Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits
Authors: Dorian Baudry
Hugo Richard
Maria Cherifa
Vianney Perchet
Clément Calauzènes
Venue: NeurIPS 2024 poster (2024)
Keywords: unimodal bandits
multi-arm bandit
auctions
Primary area: bandits
TL;DR: We prove that a specific structured bandit problem motivated by online auctions can be tackled with locally greedy algorithms.

Abstract: Motivated by online display advertising, this work considers repeated second-price auctions, where agents sample their value from an unknown distribution with cumulative distribution function $F$. In each auction $t$, a decision-maker bound by limited observations selects $n_t$ agents from a coalition of $N$ to compete for a prize with $p$ other agents, aiming to maximize the cumulative reward of the coalition across all auctions.
The problem is framed as an $N$-armed structured bandit, each number of player sent being an arm $n$, with expected reward $r(n)$ fully characterized by $F$ and $p+n$. 
We present two algorithms, Local-Greedy (LG) and Greedy-Grid (GG), both achieving *constant* problem-dependent regret. This relies on three key ingredients: **1.** an estimator of $r(n)$ from feedback collected from any arm $k$, **2.** concentration bounds of these estimates for $k$ within an estimation neighborhood of $n$ and **3.** the unimodality property of $r$ under standard assumptions on $F$. Additionally, GG exhibits problem-independent guarantees on top of best problem-dependent guarantees. However, by avoiding to rely on confidence intervals, LG practically outperforms GG, as well as standard unimodal bandit algorithms such as OSUB or multi-armed bandit algorithms.

Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits
Dorian Baudry 1.2
Hugo Richard 2+
Maria Cherifa
Clément Calauzènes*
Vianney Perchet
Department of Statistics, University of Oxford. |
2 Inria Fairplay Joint team, CREST, ENSAE Paris, Criteo Al Lab
Abstract
Motivated by online display advertising, this work considers repeated second-price auctions, where agents sample their value from an unknown distribution with cumulative distribution functioon F. In each auction t. decision-make bound by limited observations selects agents from coalition of N to compete for a prize with p other agents, aiming to maximize the cumulative reward of the coalition across all auctions. The problem is framed as an N-armed structured bandit, each number of player sent being an arm n, with expected reward r(n) fully characterized by F and p + We present two algorithms, Local-Greedy (LG) and Greedy- -rid (GG), both achieving constant problem-dependenn regret. This relies on three key ingredients: 1. an estimator of r(n) from feedback collected from any arm k, 2. concentration bounds of these estimates for & within an estimation neighborhood of n and 3. the unimodality property of r under standard assumptions on F. Additionally, GG exhibits problem-independen guarantees top of best problem- mobblemddependent guarantees. However, by avoiding to rely on confidence intervals, LG practically outperforms GG, as well as standard unimodal bandit algorithms such OSUB multi-armed bandit algorithms.
Introduction
The online display advertising has seen remarkable evolution in recent decades 14 Publishers, who are the suppliers of digital ad space the internet, sell display spots for ads to advertisers through real-time bidding in spot auctions, with many of these auctions being conducted using first or second-price mechanisms (20). Due to the technological complexity of online advertis- ing, advertisers usually delegate the task of buying ad placements to demand-side platforms (DSP) that operate many advertising campaigns. This interaction between DSP and the publisher, can be simplified as the publisher acting as multiple ad auctions selling ad impressions (online displays), while the DSP acts centralized coalition: at each time step, it determines which campaign(s) from the coalition participate to the auction to maximize their total gain. The chosen campaign(s) then compete with others to secure impressions. The primary goal of advertising companies is then to maximize the cumulative utility: the total value impressions won minus their costs. This raises fundamental question: how many ad campaigns should participate in the auction optimize the overall utility? ? the interim setting, where the DSP observes current bidder values before deciding, it's known that only the highest value bidder should be sent. However, online privacy enhancements in browsers necessitate ex-ante decisions from DSPs [8], without exact value knowledge. Here, the problem becomes challenging: choosing small number of campaigns can make difficult secure impressions, while securing the spot with a large number of bidders inevitably raises the price due
30 33
251.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).
Equua contribution.
Coorresponding author: dorian. baudry@ox.co ac. uk

---

to competition. In this paper. this problem is formalized and solved via novel Multi-Armed ArmeddBanddd (MAB) algorithms.
Problem statement Consider a sequence of T' ad impressions sold through second price auctions (see 20 for survey). At auction ( E [T', each participant (bidder) bids on the item based on its own (stochastic) value for the item. The highest bidder wins the item and pays price equal to the second highest bid. The decision maker (the DSP) runs N E N advertising campaigns forming a coalition At time t. two groups of bidders participate: (1) ne E [M] bidders from the coalition chosen by the decision maker ex-ante - without knowing the realization of the bidders' values and (2)
N' other bidders, that we call the competition. When bidder from the coalition wins the auction, the decision maker observes the realized value for the winner (also called winning bid). In the rest of the paper, the following assumptions about the behavior of bidders is made.
Assumption All bidders are identical, their values are sampled i.i.d. from a distribution supported on [0, 1] characterized by its cumulative distribution function (c.d.f.) F. All bidders bid their value.
Assuming identical bidders with i.i.d values is a strong but widespread assumption in auction theory [20 known the symmetric bidders case. It is particularly relevant in online advertising, notably in homogeneous impression markets where advertisers compete for similar ad displays due to shared objectives, target demographics, or placement competition. The bounded support assumption is also standard, as letting an automated system bid arbitrarily large values is unrealistic. Finally, bidders bid their value as this is weakly dominant strategy in this case. Lastly, assuming known number of competitors is frequently seen in auction models (see for instance [20] chapter 3.2.2). Under Assumption [ the expected reward received by the decision maker at time t is given by r(n:), where r is the expected reward function, defined by
r:nE [M] + r(n) = ( Fx.xP XF (vo) V
argmax E [m|] ig|n+p]
}
(I)
where v(1) and v(2) respectively the first and second maximum of v, and [n] is used abbreviate (1.....n} The problem therefore reduces to a MAB where the decision maker chooses arms n1. AT E [N] sequentially and aims to minimize its cumulative expected regret RT) defined by
R(T) = -r(n"))-i - with n = argmaxr(n)) r(n), "E[M]
(2)
KT
given that privacy constraints from the browser g only let the decision maker observes (1) if the coalition won, (2) the realization of the maximum value when winning.
Related works Following (2), the problem presented in this paper can formulated as a Multi-Arm Bandits (MAB, see (21) for survey). In MAB, Iearner repeatedly selects from set of actions, or "arms", each yielding a reward. The goal is to maximize total rewards by striking a balance between exploration (sampling various arms to learn their rewards) and exploitation (picking the arms with the highest anticipated rewards based on collected feedback). While the literature has known a significant development in the last years (22 7 [7]. to name few), the most popular approaches arguably remain exponential weights algorithms (EXP3, 44) in adversarial settings, and optimism in face of uncertainty (UCB, 3) when rewards are stochastic.
While UCB and EXP3 can both tackle the regret minimization problem presented here, they inevitably achieve sub-optimal performance due to not using the inherent structure of the expected reward function. Several types of structure have been explored in the bandit literature, some notable examples The problem consid- ered here is novel in the literature of structured bandits, arising from the observability restrictions coming with privacy-enhance paper the fact that r admits only one local (hence global) maximum - is in many cases inherited from this stronger structure. A typical strategy to exploit unimodality also used in this work- consists in playing a standard bandit policy (such as UCB) on a well chosen subset of arms (OSUB, (
being linear bandits (T). Lipschitz bandits (23), unimodal bandits [9] 28 29
systems. Still, in the next section we show that unimodality in this
I Last, the use of online leaming algorithms to tackle repeated auction problems have been explored in various contexts ((26) 12
32 27 ). However, none of these works approach the problem through the perspective of coalition of bidders, and are thus not applicable to this setting.

---

Table 1: Comparison of regret guarantees for different algorithms
Algorithm
Regret upper bound
EXP3
NT)
UCB1
Ene[N]
Tog(T)
A VNT)
An
OSUB 9
O
Anr41
TTg(T)
+ An-1
log(T)
Σ EnE[N]
An log log(()
A
LG (this paper)
ENEIN )
GG (this paper)
EEEB. A. + +nne A A O (log M)++ (3-))7
Outline and contributions. Section 3 presents two novel bandit algorithms: LG (Local Greedy) which is inspired by OSUB [ and GG (Greedy Grid) which combines Local Greedy and successive elimination strategy. Theorem 2 and Theorem 3 provide upper bounds on the regret of LG and GG respectively, which are summarized in Table Both algorithms achieve
regret independent of T. However, their scaling differs: the regret of LG depends on the worst local gap min Ir(n 1) r(n)l, while for GG it only depends on the gaps A, r(n") r(n). Furthermore, w.h.p. GG only suffers regret for arms in reference grid S containing O (log(N)) arms and a neighborhood B* of the optimal arm. All these quantities, as well as the notation and ON (hiding logarithmic factors), are defined in Section 3 These regret upper bounds rely on three key ingredients presented in Section 2 (1) an estimator of r(n) from feedback collected from any arm k (2) novel concentration bounds on these estimates for k within an estimation neighborhood of n (Theorem I and (3) the unimodality property
under standard assumptions on F. Lastly, Appendix D provides an experimental benchmark comparison of the performance of GG, LG and their competitors: LG has the lowest expected regret among the algorithms tested. Indeed, avoids the explicit use of the confidence bounds in the algorithm which makes it more practical, even though GG admits better theoretical guarantees.
Estimating the reward function from samples of powers of F
In this part, we put aside the sequential nature of the repeated auction setting that introduced and consider the problem estimating the expected reward as a function of the number of bidders, given a stream of collected data. We first present formulation of the expected reward function in terms of powers of the c.d.f. F. Then, we leverage this formula to introduce power estimates, as solution estimate the expected reward of an arm [A] from samples collected from an arm k E [N]. Lastly, we discuss the theoretical properties of these estimates, introducing upper and lower confidence bounds on the expected reward in Theorem
2.1 Properties of the expected reward
The expected reward function r (Eq. (1) can be expressed as function of and the c.d.f. F. Lemma 1. The expected reward function defined in Equation { satisfies,
[N] r(n) [
pptn-1 (x) pPta FPta(a)da (x)dx
The proof can be found in Appendix A. and is based on properties of order statistics.
This particular definition of r(n). which is product of n and function that decreases with suggests that r could be unimodal for some choices of F. the rest of the paper, we restrict ourselves to distributions that guarantees unimodal reward functions.
Assumption 2. F and are such that the reward function r in Equation 3 is unimodal
As the next lemma shows, many classical distributions lead to unimodal rewards for all p E N. Lemma Let be the cumulative distribution function of a Bernoulli, truncated exponential or Complementary Beta distribution. Then, for any p 19"", in Equation 3 unimodal.
3

---

The proof of Lemma 2 can be found in Appendix A.2 Note that the Complementary Beta distribu- tions [9] chosen for technical reasons, are similar Beta distributions and any Beta distribution can be approached by Complementary Beta, Furthermore, in Appendix A.3 we present experiments suggesting that is unimodal for all p E No if F is the c.d.f Beta or Kumaraswamy distributions. However, we also show in Appendix A.4 that this is not always the case, by providing a counter example. Nonetheless, we argue that (complementary) beta or truncated exponentials are flexible models for real world data, Assumption 2 is reasonable in practice. We furthermore discuss in Section 3.2
the adaptation of our algorithms if this was not the case.
2.2 Estimation of powers of
Consider the feedback W = (WA.1..... Wk,my) gathered after playing arm A and winning the auction my times. WR. represents the sequence of first values (value of the winning bid) which has been collected by arm k.
It is well known that the marginal distribution of any order statistic can be expressed as a function of the c.d.f. F (see Section 2.1 of [0]. The distribution of any element of W has cumulative distribution function F& E 1] F++P(x), which clearly exhibits one-to-one mapping between (z) and Fxx). Hence, given W k. for any l N estimate F' by
Fktp I (F)- where Putp IT
mik Σ 1(wx S 5x} (emp. c.d.f. of Wx). (4)
Estimation of Consider any arm E [NV. Following Equation 3 it appears that estimating both FT+P and pn+p-1 is sufficient to construct an estimate of r(n). According to Equation (4 this can be done from samples originated from any arm & [NV, by using the simple estimate
(( [Fntp- (x) -F dx. (FRtt
(n(n) =n
(5)
Furthermore, it also clear that any convex combination of estimates can become a new estimate, however in the rest of the paper we focus on simple estimates for simplicity.
Remark 1 (Adaptation
different feedback). similar procedure can be derived for a setting where the sequence of second prices would be observed instead. Indeed, their distribution would be reward estimate
(k + p- 1) (x))*t++ which can lead similar to (5) by using a suitable inversion formula. The same can be said for the case where both first and second prices are observed, with additional complexity because the joint distribution should be considered since for each auction the first and second price are dependent variables.
G3 I [0, 1 + (k + Fxx))ttt-11
2.3 Concentration of estimates of the reward function
We now introduce the first theoretical contribution of this paper: confidence bounds on the deviations of an empirical estimate (n) w.r.t. the true expected reward r(n).
Importance of (relatively) local estimation In principle, (5) suggests that samples from any arm E [N] can provide simple estimate of the reward function of any other arm n E [N]. However, we establish that the position of k w.rt. significantly impacts the concentration of F (n). Intuitively, the ratio(n 2 (k + p) determines how the uncertainty
E propagates the reward after
performing the inversion to obtain an estimate of Fn+tp, Indeed, considering any i E N, if for some E [0, 1] the deviation F(z)² F((x) is small then a first order approximation provides that
V (F(z)') (F())))-R(()) R(()) (F(z)' f((x) F(z))
(6)
Hence, small error on F(x)' is multiplied by (z) obtain the resulting error on F(x)² For j 2 i this term can be as large as j/i while for j < i it can arbitrarily large Fi(x) ) is very small. This observation motivates restriction on the range of arms that can be used to estimate the reward of given arm n, that we call estimation neighborhood. We use the convention that arms smaller than greater than N exist but have not collected any sample and have known reward of 0.

---

Definition 1 (Estimation neighborhood of an arm n). Assume that p 2 4 Then, the estimation neigh- borhood of n is the range V(n) = (ve(n), or [n)] = {k E [N] k p [ call (e(n) and (n)n) respectively the furthest left and right neighbor of
p-1]] We 3 (n
}]]}.
Theorem (Concentration of simple estimates), Consider any n E [N] and k E V(n). Let (n) be defined according (5) from my samples collected by k. Then, there exists some constants Bk.. (depending on n, k. p) and F, (additionally depending on F') such that, with probability 1 - -6,
21211 2+F
log 2 /
log
2 [[ mm
(((n)-r(n) S Sk.m
+ n X Ek,n,F
8
m
Furthermore, the constants admit universal upper bounds for any n, k, P, F. For instance if m& 2 it holds that By.n S 33 and "n S 100.
Proof sketch (see Appendix B for the detailed proof). The first ingredient consists in approximating the reward formulation B by a Riemann sum: for some step size D > 0, it holds that nx (n)
r(n) 3 Eem ((z,) + emp, with Vg s/D for all E {O,..., D - 13. In Lemma we use elementary properties of F to show that the approximation error satisfies erpp E [0, nD 'I. Next, we upper and lower bound (xx)) with different concentration bounds according to the value of Fk.s == F(x,) ) More precisely, for any ō E (0,1) the following bounds hold each with probability least 1 d- 6,
[P((x.) FR.O Fk.s
3log(3) ma
if FR.S Eo =
3 m
1
(Chernoff),
Fx(x))) S Glog(2/6) my
if FR.N E
8 3 3lo((26))
(Chernoff),
mx."
ma
(x.)) 00 if FR. E 12 0,
=
5
(union bound).
mm
These results are derived in Lemma 5 from a well-known multiplicative form of the Chernoff bound for Bernoulli random variables [16]. Then, the analysis consists in using the appropriate bound for each point E {0..... D - 1}. The interval do provides the first term in 7 which is dominant in terms of m&, and we make BR.. fully independent of F by carefully using some properties of the
reward function. The two remaining intervals 1 and 12 provide the second term in (7), and " depend on F through the boundaries of the interval I. The corresponding factor in Ek.,,F can be bounded by 1 or estimated in practice (see Appendix B.4).
In Appendix B we give the expression of Br.n and f and provide in 17) and 19 fully explicit upper and lower confidence bounds on Fs (n), depending on all problem parameters, and that are much tighter than what the universal constants provided in the theorem suggest. These universal constants are purely indicative, in order to assess that 3R.n and &x,,,F do not diverge for any value of the problem parameters. We now provide more high-level comments on the derivation of this result.
Discussion The proof of Theorem is non-trivial, and the careful usage of the Chernoff bounds that we introduced is crucial to obtain tight bounds on (n) for two reasons. First, it seems necessary to concentrate estimates from arms A >> n (see the discussion below (6). which are instrumental to the performance of the bandit algorithms presented in the next section. Secondly, by exhibiting powers of F, they make Sk., not increasing linearly in n, which is not easy to achieve. Indeed, it is clear from the analysis that this cost would be inevitable with standard Hoeffding bounds. However, completely avoiding seems difficult in general,
our proof provides a way mitigate its cost
by multiplying it by higher power of m -1 at least m, (if k: + 3 (n + p 1)). This is the p = 2(n + p p-p11 1) would lead to theoretically valid results, it would not ensure that the linear term in is second-order in ma.
theoretical motivation for the definition of (n) (Definition Th: while
We now conclude this section by exhibiting condition on F that allows to reduce the scaling of the confidence bound in n to logarithmic terms.
'This assumption simplifies the presentation but our theoretical results can easily be adapted for < 4if and n 1 are included by default in V(n.).
5

---

Lemma 3 (Improved bound for Lipschitz quantile function). Assume that l E v()) and F is L-Lipschitz, then there exists an absolute constant such that with probability 1- it holds that
2 mmx
log
[4[nymm
log
8
(n) r(()) - Bu.n
+ log
(8)
771
This result is proved in Appendix B.3 and shows that for some distributions (e.g. "close" to uniform) the confidence bounds converge relatively fast standard sub-Gaussian type of bounds, even for very large n. Whether this result holds in general remains open.
3 Bandit algorithms
3.1 Bandit algorithms: Local-Greedy (LG) and Greedy-Grid (GG)
We now detail the two novel bandit algorithms proposed to tackle the problem presented in Section || Both rely on the use of simple estimates of r(n) (see Section 2 by arms present its estimation neighborhood ((n) (see Definition I and theoretically motivated by Theorem [ In this section, for case of exposition, we describe algorithms as if feedback was collected every time steps. In Appendix C.I we show that the algorithms and their guarantees only require slight adaptation when the feedback is collected only when the auction won.
3.1.1 Local-Greedy
We first present Local-Greedy (LG), which is a natural adaptation of a standard policy in unimodal bandits, OSUB 19. The main idea of OSUB play UCB locally around a reference arm, and eventually reach the optimal arm n²" by gradually moving the reference arm in its direction. With LG, we adapt this principle efficiently exploit the structure of the problem considered: at each round f, LG defines reference arm le called leader, but plays greedily in the neig neighborhood (fe)), based on simple power estimates computed with samples from & only. In addition a sampling requirement. implemented by parameter E (0, 1), is used in order to ensure the good concentration of these estimates. We detail Local Local-Greedy in Algorithm below.
Algorithm 1 Local Greedy (LG)
Input: exploration parameter a, neighborhoods (V(n))nE(N (Definition I)
Play n1 and observe ~ F1+0;
initialization
for t 2 do
Set f = 14 compute (Fr, (n))ne (5q.
Compute estimates from the leader
If m, == { [t- 1]. n2 4e) S at: play n, = 4,; Linear sampling requirement
Else: play ne argmax.ev(e,) Fe, (n);
D Greedy play in V(4)
Observe partp;
D Record feedback
High-level properties of LG First, using Greedy instead of UCB is only possible because of the structure of the problem: when E, is well-explored the estimates of arms in V((a)) computed with samples from &, are sufficiently close to the true reward, so that no exploration is needed. The sampling requirement then guarantees that all greedy plays are made when E, is well explored.
second property is that since [V(&) grows with l, a sequence of locally optimal moves (best play in given neighborhood) allows to reach the optimal arm exponentially fast (in (loog(N)) steps), which is particularly interesting in practice if is large. On the other hand, LG might suffer from the inherent drawback of any "local" policy: identifying high-rewarding arm in neighborhood can take a long time if the reward curve in this area is flat (depending on how small are the "local" gaps). This problem can be attenuated, but not solved, by adding initial exploration phase. We propose Greedy-Grin presented in the next section, as a way to fully address this issue.
Lastly, requiring only the computation of empirical reward estimates is a strength of Local-Greedy. Indeed, deriving tighter confidence bounds would improve its analysis, but not the practical imple- mentation (and performance) of the algorithm.

---

3.1.2 Greedy-grid
The concept of Greedy-Grid is very intuitive: it plays a Local-Greede strategy only if it can tell which segment of the reward function contains the best arm with high probability. To implement this idea, GG uses Suucessive-Eliminatio procedure [13] on subset of arms forming reference grid, denoted by S.
Reference grid The grid S is designed so that two of its successive arms belong to their respective neighborhood (Definition[]) []. and can hence mutually estimate themselves and all arms in between (Theorem D). In particular, the optimal arm can be well-estimated at least by its two closest neighbors on the grid, so its neighborhood can be "discovered" with high probability simply by sampling the points in the grid in a round-robin fashion for sufficiently long time.
Following Definition| I
we construct S = {sthe> recursively; $1 1, and for i 2 2 we set 8(41 max {s 2 s; : [N] s E s( s, E V(s)). We provide an illustrative example below.
Example 1. For N = 2000 and = 100 the grid is S = {1, 50, 123, 233, 398, 645, 1016, 1572].
Any arm n [N] admits left and right "neighbor in the grid". denoted respectively by of (n) S, re (n) N + 1 if and os (n) and defined by: (n) = 0 if (y x) otherwise. We call the "bin" of arm n all (uf (n), of (n)) argmin ne(s.w) arms between its left and right neighbors: B(n) = (n E [N], (n')) < n < of (n')). For simplicity we use the notation B* = B(nn*
max S and
Greedy-Grid We provide the detailed implementation in Algorithm 2 below, and now describe the general principle of the algorithm. At each round, it operates in two steps. In the first step, it decides whether to play arms on the grid S (play the grid, to simplify), or to focus on specific bin (and, as we will see, play greedy). This choice depends on an elimination procedure: an arm in S should be eliminated for this round if their upper confidence bound (UCB) is smaller than the best lower confidence bound (LCB) among all other arms. Furthermore, if there exists an eliminated arm whose index is closer to the index i of the arm with the best LCB, then the unimodality assumption implies that h should also be eliminated. The set of arms not eliminated at t is called C2 in Algorithm 2
To compute the UCB (U₂) and LCB (L,) of an arm we elect a leader en which is the amm in [uy (n),, u (n:) that was played the most the last rounds and then compute the bounds based on
ln using Theorem [ We show in the proof of Theorem 3 that this procedure ensures that linear number of samples in is used to compute the UCB and LCB of arms in B* with high probability.
If at least one arm is not eliminated (C, is not empty), arms in Cr are played one after the other (Round Robin). If all arms in the grid are eliminated, GG plays greedily in the bin B(i;) of the arm with the highest LCB. The empirical reward of each arm E B(it) is computed similarly as Un, and Ln using samples from the leader 7,. GG then plays the best empirical arm at times which is the same sampling requirement as LG.
The careful design of Greedy-Gria prevents the main theoretical drawback of Local-Greedy since the algorithm has a very low probability to play in a sub-optimal bin, it almost never pays "local gaps" in sub-optimal part of the reward function. However this guarantee comes a cost: if nz" is not in the grid, it will never be played until the confidence intervals shrink "sufficiently" to eliminate the entire grid. Hence, GG might be more conservative than LG in practice, while offering better theoretical guarantees, We express this trade-off in the next section.
3.2 Regret upper bounds
We now present the theoretical results obtained for the two algorithms presented in Section 3 We first establish the regret bounds and sketch their proofs, before discussing and comparing the results. We introduce some notation, that considerably simplifies the presentation of the results.
Notation: Ô and O For any 0, we the notation (zx) describe quantity that scales in I, up to logarithmic terms in r and N (hence the notation is linked to the problem). Furthermore,
'We assume unique optimal arm for simplicity, but the analysis holds if several successive optimal.
7

---

Algorithm 2 Greedy Grid
Input: Grid S, confidence levels (ōt),EN, sampling parameter a
Play min S and observe w ~ Fu1+p
for t do
my
Vn E [N] en = arg (f) (m)] Hu E (t - 1) = kH]:
D. Elect leaders
Vn E [N], In Ine, (n, 5,) and Un = Uc, (n, 5n)
D Compute UCB LCB 22
nr(m In;
Compute best lower bound index
C. {a S Vs E [N] s. t. a S s & or arr220 s 2 2 b;;; Non-elim. grid arms
if n4 (it)) and m S at then
> Ensure linear sampling for bin plays
L Play n, = n1
else
Play grid if non-empty greedy in the best LCB's bin L Cf 2: Play Round Robin on C;; Else play argina fr., (n)
Observe w ~ ;
> Record feedback
for n E [N] we also use Ön as a shorthand notation for Ö((n' V Vz A n²x). This type of constants emerges from using (7) (Theorem[] in the analysis. Indeed, we proved that the simple estimate of an arm n by an arm E V(n) admit Gaussian ("square-root") confidence intervals, independent of n, when the sample size of & is larger than ((n)).
Theorem 2 (Regret bound for Local-Greddy). Lef A == min Ir(n + 1)
r(n)] (worst local
gap). Under Assumption 2 and with a = (logs/2 N + 1)-1, 1 the regret of LG is upper bounded by prohlem-dependent constant: there exists (Cn (Cn)nE|NTA each satisfying Cn = ON ( ( such that RT S Eme[N] Cn.
Additionally, if the arm set forms a single estimation neighborhood. that is Vn E [N] V(n) 5 [N], then each constant Cn can be refined to On (A,i",, providing Rx- = Ö(VNT), which holds even when the reward function is not unimodal.
Proof sketch (see Appendix C.3 for the detailed proof). We start by the case where the arm set forms a single neighborhood. Since LG is guaranteed that any arm it selects will provide an estimate for all the other arms, this context is very similar to full information scenario. This explains why GG achieves both constant regret depending on the gaps, and a gap-independent bound in vNT. Furthermore, the hidden logarithmic constants come from carefully using Theorem to separate the linear term in from the gaps when they are small.
The general case presents an additional complexity. Indeed, it is possible that playing arm n + n² is locally optimal, if n is the best arm in the neighborhood of the current leader: playing n in that context would not be unlikely. To tackle that scenario, we prove that pulling arm n at time necessarily implies a locally sub-optimal play, in some estimation neighborhood, at some point in the past (maximized by the chosen value of a). We then show that this cannot happen after some deterministic time w.h.p., leading to constant regret. However, since the sub-optimal play might be any arm the constant now depends on the worst local gup A
Theorem (Regret upper bound for Freedy--Gridh Suppose that GG is tuned with confidence level 6; Nop3, and a 1/4. Then, for any T E N it holds that
1n > n²) ))
R₁ = ÖN
Σ nE
1
log(T) An
Ad
[[n<nn)
An
A2 (((n))
A (xr)))
NES
Additionally, holds that Rr = Ō (V((K+
B+ITTT
for K [l0g)/2(N)]
Proof sketch (see Appendix C.4 for the detailed proof). First we prove that, w.h.p., during linear time range in GG either played the grid or in B* Hence, arms n E [N]MS U B*) are played a (universal!) constant number of times by GG in expectation. Then, for S the term in log(T) comes from the standard analysis of UCB 3 while the constant bound comes from exploiting that after
8

---

a constant time n the LCB of n² eliminates its neighboors w.h.p., and by extension the entire grid. Finally, the constant bound n E 8 derived similarly as the first bound of Theorem
Discussion First, we show that being able estimate r(n) from the feedback obtained after playing an arm & in its estimation neighborhood leads to a regret independent of 'T for both LG and GG. For the former, the bound depends in general on the worst local gap A, while for the latter only the actual gaps An (with n²) are involved. This difference permits to obtain a problem-independem guarantee for GG
for any configuration of p and N. Furthermore, its scaling VK + [B*| S v 2n + [10g3/2(N) (N)J can
be much smaller than VN if n² is small.
Then, we would like discuss the impact of the concentration bound presented in Theorem on the regret of both GG and LG. Indeed, a naive approach with Hoeffding bounds would not allow to remove n from the first order term of the concentration bound, because of the multiplicative factor n in the defimition of rn)). A feature of our concentration bound is that the linear scaling in does not appear in the first order term. Informally, this allows to exhibit terms of order Ö~ (A,²) in the regret analysis instead of Ó(N2 " which can be significantly better for small gaps. A remark here is that the size of the grid in GG could be optimized as larger grid makes the second order term in Theorem
[
smaller but is paid linearly in the regret.
We nevertheless highlight some potential for improvement in the analysis of LG. First, the local gaps A in the bound of LG could be replaced by (in spirit, referring to S for simplicity) min |r(uf (n)) r(us (n) It is clear though that this gap remains "local" and can be arbitrarily smaller than A, for some arms E [N], so the general interpretation of the results would be unchanged. Second, for simplicity, the analysis of LG was carried out using the constant upper bound of 32,n and EK,,, but a tighter analysis could lead to a better dependency with respect to N.
We now justify the use of simple estimates in GG and LG. In practice, combining estimates would allow to use more samples for the estimation. However, this would make the algorithm slower, and we believe that the sampling requirement implemented in the algorithms makes the use of simple estimates efficient: potential uniform exploration in a neighborhood is replaced by focus on single arm, but the same quality of information is accrued. Furthermore, from a theoretical perspective union bounds over the samples collected by each arm might also cost a factor N in the analysis.
Lastly, while GG admits better theoretical guarantees, LG might be more appealing in practice because it does not require to explicitly compute confidence intervals. This means that the regret bounds provided for LG are conservative, and might be refined with tighter confidence bounds without changing the algorithm.
Adaptation for non-unimodal rewards While LG relies heavily on Assumption 2 GG can be readily adapted handle non-unimodal reward functions. This is done by modifying the definition of the set of non-eliminated grid arms C, to {s E S, U, 2 LG} in Algorithm 2 In that case, the algorithm can no longer eliminate arms the grid based on the elimination of other arms. This naturally induces that the number of plays of sub-optimal arms is no longer bounded by a constant. In Theorem 4 (see Appendix), we show that only the Olog(T)) term persists for n E S in Theorem 3, while the
bound remains unchanged. Although we believe unimodality necessary for achieving constant regret, this result demonstrates that, even without that assumption, GG can still provide the same logarithmic regret guarantees as UCB. However, it does so on a |S] armedd bandit, rather than an N-armed bandits with |S| (log(N)) < N for large N.
Experimental results In Appendix D we present a benchmark of LG, GG, UCB, EXP3 and OSUB on synthetic data in terms of the expected regret R(T). This benchmark illustrates the strong performance of LG relative the other approaches. Although GG offers more robust theoretical bounds, LG proves to be more effective
guarantees, particularly with sub-linean in practice. Several factors may explain this gap between theoretical guarantees and empirical performance. First, as discussed in the previous section, the worst-case local gap in the analysis of Local Greedy (Theorem 2 might be overly conservative. This worst-case scenario could occur under a combination of unfavorable conditions, such as poor initialization far from the optimal arm and a flat reward function, paired with bad luck in exploration. However, such a scenario is likely rare practice and was not encountered in our experiments. Additionally, Local Greedy benefits from scenarios
9

---

where it starts playing in the optimal neighborhood only after few steps, situation GG cannot exploit due its need for sufficient statistical evidence eliminate all suboptimal neighborhoods. While GG's caution leads to stronger theoretical guarantees, this comes at the cost of empirical performance. Moreover, GG's results are tied the tightness of the confidence intervals in Theorem 2 limitation that does not apply to LG. An interesting and challenging open problem remains whether LG can be modified to achieve the same theoretical guarantees as GG without sacrificing its performance. We leave this question for future work.
4 Conclusion
The bandit problem studied in this work is structured since playing arm n gives a reward r(n) determined by n. p and the unknown c.d.f F and with probability xtp the distribution with c.d.f patp.
an observation of sample of
While traditional bandit approaches give problem dependent bounds depending on T, algorithms GG and LG presented in this work have constant problem dependent bounds. Furthermore, GG and LG avoid a quadratic dependency in N for large thanks to new concentration bounds introduced in Theorem I Overall, while GG has the best theoretical guarantees, LG has better constants and is therefore better suited for most practical problems (see the discussion at the end of Section 3 and experimental results in Appendix D)
Whether an algorithm that has the theoretical guarantees of GG and the practical performance of LG can be designed is an interesting question. We believe that the main leverage improve the practical performance of GG might be to derive tighter concentration bounds. Possible directions to improve over Theorem 1 might include: further refining the decomposition of the integral in 3 according to the value of F, further use "empirical" components (depending on estimates of F), or even using ideas from the proof of the DKW inequality (24 to avoid the union bounds over the points of each interval in the decomposition. We leave these directions for future work.
To conclude, since in practice, DSP can launch campaigns through multiple auctions, an interesting question is whether the current analysis could extended the case of auctions where a play at time is (Ma)))aE[A) where EeE[A) Ru,1 N and the reward is Ege(A) Na (n),,) with ra determined by integers Pa. Ra, and F, in the same way that depends on p, n, and F. How explore each auction in parallel in an efficient manner and how to handle the case where some auctions must be assigned zero players then the main questions to solve.
Acknowledgments
Dorian Baudry thanks the support of the French National Research Agency: ANR-I9-CHIA-02 SCAL, ANR-22-SRSE-OON funded by UK Research and Innovation (UKRI) under the UK government's 's Horizon Europe funding guarantee [grant number EP/Y028333/1].
Ocean, and ANR-23-CE23-0002 Doom. Dorian Baudry was partially
Vianney Perchet's 's research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project was also funded by the European Union (ERC, Ocean, 101071 10071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
and through the grant
DOOM ANR-23-CEE23-002
References
[1] Y. Abbasi-yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, edi- tors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL httph:tt/ttppseeeeettses eribbeatff244477dddddeerssseeeee
www.ips...pp.... cttppp.cccpaaaee httppappr_ffleee wtt.ff/ll///appee//////eeee .df
[2] Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem.
In Proceedings of the 25th Annual Conference Learning Theory, 2012. 2
10

---

[3] P. Auer, N. lem. Machine Learning. 47:235 256, 2002. URL httpp://appt semanti cccholarrr org/
and P. Fischer. Finite-time analysis of the multiarmed bandit prob-
CorpusID: 607694
8
36
[4] P. Auer, N.
Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48 77, 2002. doi: 10.1137700975557119937..
htRts:ts::/doo org/ 10. 1137 / ///////0005539009993333
36
[5] M. Babaioff, Y. Sharma, and A. Slivkins. Characterizing truthful multi-armed bandit mech- anisms: extended abstract. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, page 79-88, New York, NY, USA. 2009. Association for Comput-
ing Machinery. ISBN 978 605584584.
doi: (41144//156674415666633
URL https
7/doi org/ 1145/ 116474115777.... 1566386
[6] D. Baudry, N. Merlis, M. B. Molina, H. Richard, and V. Perchet. Multi- Aumdi- bandits with guaranteed revenue per arm. In International Conference Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain, Proceedings of Machine Learning Research, 2024. 28
[7] O. Cappé, Garivier, O.-A. Maillard, R. Munos, G. Stoltz, al. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, 4163):111-15541 2013. 2
[8] Chatterjee and Sharfi. Bidding and auction services in the privacy sand- box. https://githuu: blob/main/bidding
sinctioonssevicoo api. aww.mm..mm.............. md 2024.
[9] R. Combes and A. Proutière. Unimodal bandits: Regret lower bounds and optimal al-
gorithms. ArXiv, abs/1405, 40565096, 2014.
URL https: http://c/..eemmaiicccccll..a.a org/
IorpusID:A0 15210477
36
[10] H. David and H. Nagaraja. Order Statistics. Wiley Series in Probability and Statistics. Wiley, 2004. ISBN 9780471654018.
URtpsstss///bok wwwgge.ooooo...ooo.oooooo.o..... froolleffr/books...
4
13
[11] Y. Deng, N. Golrezaei, P. Jaillet, J. C. N. Liang, and V. S. Mirrokni. Multi-channel au- tobidding with budget and roi constraints. ArXiv, abs/2302.01523, 2023. URL https
//api. peapi.semanticccho.... www.sccchhhaaooooooooooeoeeeo I :5:59998278
2
[12] N. R. Devanur and S. M. Kakade. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, page 99-106, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605584584, doi: 10. 10.1145/1566744.556663
URL httpps////// http///do.ooro////// 1141/1166374444 11115666774116668888 1566388
[13] E. Even- S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi- bandit and reinforcement learning problems. Journal of machine
learning research, 7(6), 2006. 7
[14] L. Ha. Online advertising research advertising journals: A review. Journal of Current Issues and Research in Advertising, 30, 05 2012. doi: 10. 10.10/0/00411342200008 10505233. I
[15] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchaant K. Sheppard, Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Array programming with Sept. 2020. doi: 1111038//4158--000--69999 URL 2649-2
NumPy. Nature, 585(7825) https://doi.ors wwt.:///.1111//111111
35
[16] W. Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426, 1994. 18
[17] Honda and A. Takemura. Non-asymptottic analysis of new bandit algorithm for semi- bounded rewards. Journal of Machine Learning Research, 16:3721-3756. 2015. 2

---

[18] J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9
(3):90-95. 950 2007. doi: 10.11099CC522200..555 35
[19] M. Jones. The complementary beta distribution. Journal of Statistical Planning and Inference.
104(2):329-331) 2002. ISSN 0378-3758. ottp:////ooooooggooooooooooo1110
URL https: /wwp://wwwww..o www.ssceieeerrrrt...o wtt.a///ccaaaaaaaatt///////////0
4
[20] V. Krishna. Auction Theory. Academic Press, 2009. 12
[21]
T. Lattimore and C. Szepesvari. Bandit algorithms. 2017. URL. httpp:://boo-llatiinng
com/dowmloads/ bockks//oooobboo book. pdf
[22] Levin. Auction theory. Manuscript available at www. stanford. edufjdleviin/econ, 20286, 2004. 2
[23] S. Magureanu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. M. F. Balcan, Feldman, and C. Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 975-999, Barcelona, Spain, 13-15 Jun 2014.
[24] Massart. The tight constant in the dvoretzky-kiefe wiefer----ieewwweeee woofewtwoooowttttz incquality. The Annals of Probability, 18(3): 1269-1223,,,,, 1990. ISSN 0091 1798. URL http://wwwe jstor org/
stable/2244426 10
[25] S. Muthukrishhan. Ad exchanges: Research issues. In Workshop on Internet and Network Economics, 2009. URL TRLhttps:: https: www.nticschooleete......e wrwp/oooooSI: 10046036 [
[26] H. Nazerzadeh, A. Saberi, and R. Vohra. Dynamic cost-per-action mechanisms and applications to online advertising. WWW '08, page 179-188, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 978 105588052.
doi: 10. 00.1145/36744771337555 URL
https://doi. org/10. 11444/1366499713672222 1367522
2
[27] T. Nedelec, C. Calauzènes, N. El Karoui, and V. Perchet. 2022.
[28] S. Paladino, F. Trovò, M. Restelli, and N. Gatti. Unimodal thompson sampling for graph- structured arms. In S. Singh and S. Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligncee February 4-9, 2017, San Francisco, California, USA. AAAI Press, 2017. 2
[29] H. Saber, P. M'enard, and O.-A. Maillard. Forced-exploration free strategies for unimodal ban- dits. ArXiv, abs/2006. 16569, 2020. URL htthh::tt//pppp semanticscholeee.... wwwpechoolarrooooooouuuuo 220265988
[30] A. S. Sashhi-Roshkhar. Real-time bidding in online display advertising. Mark. Sci., 37:553-568, 2018. URL hht.th:tt//aapppa http:///ppp.ssmaaniiiieccc www.seeeicaanollaeo..eeeea org/Corpusil
: 52277027
[31] P. Virtanen, R. Gommers. T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weckesser, J. Bright, S. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, Í. Polat, Y. Feng, Laxalde, Perktold, R. Cimrman, I. Henriksen, A. Quintero. C. R. Harris. A. M. Archibald, A. H. Ribeiro. F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:261-277 2020. doi: 10.1008//411999 592-019-006666
E. W. Moore, J. VanderPlas,
35
[32] J. Weed, V. Perchet. and P. Rigollet. Online learning in repeated auctions. In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1562-1583, Columbia University. New York, New York, USA, 23-26 Jun 2016. PMLR. URL http::://p/sttt httpss://proceeednngss mlr. wtwp:iisnnnmmm..sssss.//sseesese press/ v49/weed16 htm
2
[33]
Y. Yuan, J. Li, and R. Qin. A survey on real time bidding advertising. Proceedings of 2014 IEEE International Conference on Service Operations and Logisties, and Informatics, SOLI 2014, pages 418-423, 11 2014. doi: 10. 10.100//501122014666666.1
12

---

A Properties of the expected reward function
In this appendix we prove the results presented in Section 2.1 of the paper, and discuss the shape of the expected reward.
A.1 Proof of Lemma
Lemma 1.
The expected reward function defined in Equation 1 satisfies,
n E [ + r(n) = ( pptn-1(2)) - FP (x)d(x)dz
(3)
Proof. Given (ci)vE(mtp)
F F, we have
argmax E [n]] }
r(n) = E
(v(1) v(2)
rE(ntp]
E
(v(1) v(2))
E 1 argmax i E [n)]
iE(n+pl
(4)
E v()
E V(2)
n n+
n
x
P(v(2) > x) - P((((2) > x)dæ
n +
n
x
P(V(2) S x) - PP(())) S x)dx
Ti +
(161)
n
{ ((n + p (x) (n p 1) (
n+p p
(Fntp--(x)) pm (z))dr
The first equality is the definition of rn) in Equation ( Equality (i) follows by independence of the index of the maximum and the value of the maximum and second maximum. This is itself consequence of the fact that the values are i.i.d.. Then equality (ii) follows since the distribution of the index of the maximum is uniform over n + p. This is also consequence of the fact that the values are i.i.d. Lastly, equality (fit) follows from [10] (Equation 2.1.3) where for k E {1, (1,2). it is shown that
atp
n (MT²)
P(V S x)
Σ im=+p--++ 1+1
(1 F(z))ato-i(())
i
and the proof concluded by substitution.
A.2 Proof of Lemma 2
As preliminary, we formally define non-usual distributions considered Lemma 2
Truncated exponential distribution Let a > O be some parameter. Then, we define a truncated exponential distribution of parameter as the distribution with c.d.f. F F(0) and F(1) and the density of this distribution is the same the density of the exponential distribution with same parameter on the segment [0, 1). up to normalization constant.
I-c T-c-a Hence,
Complementary Beta distribution
Lemma 2. Let F be the cumulative distribution function Bernoulli, truncated exponential Complementary Beta distribution. Then, for any p E IN*, r in Equation 3 unimodal.
Proof. We consider each family of distributions separately.
13

---

Bernoulli distributions F the c.d.f. of (gg) (a Bernoulli distribution of parameter q), then r(n) is equal to the probability that exactly one player from the coalition draws a value of and every other player draw value of 0. Hence, we obtain that r(n) ng(11 q)*+p=1, which is trivially unimodal and maximized in n' log(I-g) regardless of the size of the competition.
Truncated exponential distributions Let a > O be the parameter of the distribution. Let Q(x:)
be the inverse function F (the quantile function), defined by Q(x) 1/2 log (T-x(I-e-m) a
k=
Let's denote by q(x) the derivative of (z)), denoted by g(x) = Etso Aet where du (1-e Introducing theses functions allows us to rewrite r(n) as follows,
r(n)
(1-F(u))
pptn-1(1 (1 (1- 2)q(x)dx
using F(v) x
+00
ptn-1 (1 (1- (1=x) x)
Σ
Aet
dr
+00
n
n
Ak
p k +1 p n
k=0
n
An + n
(Aj - \--1)
n
n k+
j=1
Ao
p
+
t00
- + (a, 21-1)
p+j j
n p+p
j=1
to0
p+j
= >o
+
n n+p p
A
where the last inequality follows since limy- Ag- = 0. Remark that 0, 2 0 since X is decreasing and Σラ= 0g
The derivative of r(n) is given by,
02 p+j
((n) do in + +22
(n + 5)2
j=l
= =00 - Σ 0,0 0000pt((n)
1=1
= =100p(n) Σ 0,L (n))
where I (n)
2 pp)
(p(n)
the functions 1 1ppp45 (n) are non-decreasing hence it is the same for their convex combination. As sign(r'( = sign(1 - D3= 0,1 (n)) follows that sign(r'(n)) is decreasing meaning r(n)
unimodal.
Complementary beta distributions Using the same change of variable as in the previous proof (Y' F(X)), we express the reward follows,
r(n)= = n x Ey-q (y-tp-((-Y))
where Q denotes the quantile function associated with c.d.f (i.e. F-1). By definition of F, Y follows Beta distribution of parameters (a, b). We can thus compute the expected reward by using
14

---

the explicit formula for moments of the Beta distribution,
p-
n+p-1
E Ex-B(a.
(xm x
II
a a+k
II k=0
a a
a+b+ k
a+b+k
k=
n-p-2
1
+ n
a a+ k
a
1-p-1 p-p-2
a a
X a+b+n+タ-
a+b+k
k=
Thanks to this expression, we prove the unimodality by analyzing the ratio
r(a+1) r(n).
tthat first write
as
n n+1 atntp-1 r(n 1)
a+b+n + +
x
x
r(n)
n +
a+b+ntp
n 1+11 1 atn+p-1
n a+b+n+p
and then obtain that this ratio is larger than if and only if
(n + 10 n p 1) 2 n(a + +b bb n(a +la+n+pp + + p 12 n(a + p) + bn
+ p-
which concludes the proof by showing the unimodality and expressing the value of the critical point.
The proof of LemmaaZhigllights that the unimodality assumption satisfied as soon as the quantile function, expressed power series, has its coefficients that slowly decrease (indeed, the k-th coefficient just needs to be smaller than 1 1- times the k 1-th one).
Similarly, the second proof technique highlights (up to standard algebraic manipulations) that unimodularity is guaranteed soon as the function n + 1|1 2] is log- concave.
A.3 Additional discussion the unimodality of
In this section, we plot the shape of r(n) for some additional families of distribution that conjecture to be unimodal from the plots.
Beta distribution The following figure, illustrate the unimodal shape r(n) for different parame- ters for the Beta distribution and p.
15

---

He(2, 5), p-2
#e(3, 3), p-70
ne(3, 71, p=:0
#e(1, 3),
R(n)
0.41
103
13%
100
Figure 1: Shape of r(n) when F Beta
Kumaraswamy distribution The cumulative distribution defined by F(x) = 1- (1- (1-x") )²) for some parameters (a. b) (we use the notation K (a, b)). The following figure, illustrate the unimodal shape of rn)) for different parameters K (a, b) and p.
0.4
K 4), p-2
R(n)
Kt3. 5), p-4
XV0.2. 0.2), p-10
0.50
XV0.2. 0.4). p-12
0.2
Figure Shape of r(n) when F is Kumaraswamy distribution
We now provide and discuss an example where Assumption 2 is not satisfied.
A.4 example of distribution with non-unimodal rewards
Let us consider discrete distribution supported on {0, 0.5, 1). The counter-example emerges from putting all the probability mass 0.5: let us consider small e > 0, identify F with (t, e, 1) and assume that there is no competition (p 0). Then, we can verify with (3) that
r(n)
e)" n- (e + (1-))")
(1 e) +e( - ()11-))=1)
Consider 0.15, get up precision 0.001 the values: (r(n)) (0.5, 0.255, 0.191, 0.190, 0.197, 0.200, 0.198)
showing that rnn) is not unimodal in this case.
16

---

B
Concentration bounds on simple reward estimates
B.1
Auxiliary results
Before presenting the proof of the theorem, present two auxiliary results that are essential to its development.
B.1.1 Riemann sum approximation of the expected reward
The first result consists in upper bounding the deviation of a Riemann sum approximation of r(n) (for some n E [ND with respect to its exact integral formulation. This result is also of practical interest, since it can prevent computing exact integrals each step of the algorithms without altering their theoretical guarantees with an appropriate tuning of the approximation error.
Lemma 4 (Riemann sum approximation of r(n)). Let E [N], D E N, and define the grid
(cs)sEE0.....DD.1 = {0, 1 b......0 - }. Then, the expected reward approximation
D-1
F(n)= = n (((x)) - -F ((xx))tt)
Σ
satisfies
Inn)- S D
Proof. For any j E N we consider
S
-
D Σ (x.)
approximation of 1 = S' F (x)dx..
S=0
We recall that since FJ is c.d.f., it is monotone, increasing and satisfies FJ 0 and F² (1) 1. This means that for any s E {O...., D 1}. it holds that Va E [041) PD (Ix)) S p2 s F$ (x.+1). The linearity of the integral first provides that
1 1= / F'(
D-1
= Σ ==0
(x)ddr
Then, using this decomposition and the monotony of FJ obtain that
D-1
D-1
S₁ S
Σ
FJ
8
(x)dd S
Σ
D
D
D
D-1
<
Σ
Σ
F
(
s s+1
- F5 (
K=0
$ ΣF
1
F (1) (1())
D
S +
Therefore, we obtained that for any j E N it holds that 8, < S Sg D- We conclude by using this result after splitting the reward as a difference of two integrals that can be expressed in this form, respectively with j n + p - and j n + p.
B.1.2 Chernoff bounds for Bernoulli random variables
In the following lemma, we summarize the different concentration bounds that we use the proof of Theorem
17

---

Lemma's 5 (Muttippliaaiive Chernoff bounds), Let Pm be the empirical average of m i.i.d. Bernoulli random variables X,...., ,,m with expectation Js. Then, for any 8 >> 0, each of the following bounds holds with probability al least 5,
7m 1 V 3lng(
(2/88)
if E 1o
61og(2/8) Um I
if E 11
6
3 3log12
m
m
m
Am
if E 12
[0. m.
Proof. We first tackle the case ja E I2, where the bound is obtained by remarking that P(um > 0) < P( [m] x; S my S 6. The two other cases are obtained by using the multiplicative form of the well-known Chernoff bounds (16), that provide that
vy > 0, P( 2 (1 7) S e
and
Vy E [0, 1J, P(pm (1-7)14) S - 22
When considering S we can further write that
P( μ 2 qp) S 2c
On the other hand, for y 2 the bound for the lower deviation is trivially 0 while the bound for the upper deviation can be written as follows,
7 = Pm 2 (1 + 7)4) S e - 2 S
mm
Hence, the case separation between the intervals Io and I simply consist in identifying the value je for which probability - 5 can be obtained by setting an appropriate [0. 1] or for in the
3 log (3)
above inequalities. More precisely, inverting the first bound provides
which is
valid only if μ プ log 3
3 log {) This leads to the first confidence interval when
< 1
E 1o. The same procedure for μ E 11 leads to = 3lom(3) ()) which provides the result stated in the lemma. This concludes the proof.
B.2 Proof of Theorem 1
Theorem (Concentration of simple estimates). Consider any E [N] and k E Vnn). Let Pi be defined according to (5) from my samples collected by Then, there exists some constants Be (depending on n, k. p) and Ek (additionally depending on F) such that, with probability 6,
log
2 [Inymo
log
(2[nm/mx)
kT
5
(F(n)) -r())] S Bu,n
EN.,,F
mk
171
Furthermore, the constants admit universal upper bounds for any n, k, F. For instance if m& > 4 holds that Ba.n. < 33 and " < 100.
Proof. We build the proof from the Riemann sum approximation of the reward presented in Lemma and the Chernoff bounds presented in Lemma 5 Defining some parameter D N that will be fixed later, we use the first result to consider the following approximation of the empirical reward estimate (n) by
FA (n( = D
1
D-1
Σ
PR+p.mA
8
ntz-1 E+P
P Fk+p.mx
F+P
Thanks Lemma
we know that Fa E (Fa(n) n, (k() 3. For the of proof,
introduce the notation Fd
F ( for any j [N], ENtP Fa+p.mx ($), and F. ka
18

---

FRtp.mo (z) 1 so that
(x(n) Σ
Pa Pa Padkn)
that we want to relate with
1 D-1 F p2ttt)
F(m) = D
We that each variable PaR can be expressed as the expectation of mg i.i.d. Bernoulli random variables expectation Fl+t,, since Fk+p.m,
Σ [(Xx, I x}. Hence, we can use the confidence intervals providing by Lemma according to the value of Fk We define two critical values, corresponding to the switch between the different intervals To, J1 T2 in the lemma, and their closest upper point in the discretization grid. The first
J0,k F-1
and 80, [Dro,
and we recall that below TD it holds that F with probability larger than - 5. Then, we define
log
1 F-1
and 81, = [Dri
We remark that We do that for technical reasons, that we will motivate at one stage of the proof. These terms depend both the sample size my and the confidence level 5, but omit them in the notation for simplicity. Then, for fixed values of these constants we decompose the estimator between the
multiplicative factor 4 inside of F-!, while Lemma might suggest to
intervals To (si,,,..- D 1). I1 {So.A..... $1.8 1}. and T2 = (0.... 80, 1). Note that for the second interval to be non-empty it must hold that 8o, I 81,1 1, that we assume in the
following, otherwise can just remove this interval from the analysis.
For 2 81,4, Lemma g guarantees that with probability larger than 8 holds that
log (2)
pk+p [(1 - 7s) Pk-P (1) Fktt] for 7/+ = F3 +
my
while for S 81,8 - we can use one of the two other bounds provided in the lemma. Using union bound, all the confidence intervals hold simultaneously for the points in the sum and in F with probability larger than 1 -D 1)8, which defines a "good" event
wk l2, pktp O, Vk E 11, Ektp < log
Vk lo, FRtD E [(1 (11 F (1 7:) F
For the rest of the analysis, we assume that & holds. In particular, that context there exists $1,k constants (Za)se(er D-13 such that Vs E lo, Fkt+p = (1 2,) Pktp and =, E (s),. We now upper and lower bound (in(n) using these constants, first writing that under G holds that
D-1
Fi((n)
1
P Pa -F Fark.))
D
x=0
D-1
81.--
1
p Pa.knn1 Park.))
1
Σ
p Fa.ka- - Panan)
D
sm81k
D-1
$1.-1
= 8=8L
Σ
((1+
p-p-1 pm+p-1
(1 + 22)
adp
+
Σ
(Fekn-1 - Fenhi))
8=80
19

---

where we used that all the terms are zero for indices smaller than so,k- We can thus express (n) as follows.
(m(m)) F(n)) + nEo + nεi,
with
Eo Σ ((1+
"
1)
1
Σ ((1 23)
25) EiD 1) and
D 1
S
$1.
& (Pah,n-1-Pe P Palkn)
-
Σ
(FutD-1-FF Futt))
so we can upper and lower bound Fi(n) by upper and lower bounding & and & separately.
Bounding the individual terms of Eg For any à 2 $1,k we consider the term
Ea,s ((1 + 2x) " 1) F ((1 + 23) E+g 1) Futt..
We first re-arrange it in a more convenient way, remarking that F
Fn+e-1= Pn+ (Fs, + - F1)F = P Fm+
F pm-Dー16 (1 (1- F2).
Using this result, we obtain that
Ea. == ((1 + 2x)
bFF 1)F ((1 + 23) Ftr 1) Fr
née
= ((1 + 2z)) k+p - -1)P + (1 F,)) - ((1 + 2の) ) 1)F
= P + 2x) - 1) (1 + 2,) ## + 1) - Fut (11 - F.)((1 + 2n) + - 1),
which simplifies
Ev.. = P + + 2g))
vle
(1 + 2
patp-1 (1 F.) zg)
(10)
E
We remark that these two terms have opposite sign, Et. having the same sign 2g. We first upper bound Eo.., starting with the case 2g > 0, for which it holds that
0 Ev., S Et. < ((1 71) ++ 1) p (1 F.).
The constant C₁ is explicit from the definition of 7s. and the bound holds for any E [N + p] without restriction. However, if we only consider the case p-p-1 < 2 then we can further write that
c, (1 + 76)2 since % S 1 for the values of considered. Then, for 2g S 0 we use that
2% 7 S 3%
2g S = E, S E7 S F ((1 + 2.)
ptp-1
(1+ 2z)
pn (1 + 2.) x#F
(1 (1 + 2. K+F
Using the notation y/- = -2 for convenience, we upper bound the last multiplicative term as follows,
leg(i-ms)
log( 1 ye)
(1 ys) ド+F e
k+#
21 +
1: ++p p
V/8
log
1 +
k + p
ya
1
ys
+ p
yo
20

---

which leads to
Us = -2 2s 2 0 + Eg, S E0 I F - ys))
m-p-1
ys
+ ys)
= P(1 Fm-
ys)
nip
ya
k+p
We now remark that when k p S p then the bound simply becomes Eú., S PTPP ktp' However, when k+p > n+p-11 1 the upper bound is diverging when ys gets close to 1. Since the upper bound is increasing in 7/s and using that n + - N (Ac + p) we obtain that E0 S Frtt 7
<(1-))
This is the motivation for calibrating the threshold $1 so that 2 81,8 + (1 - 75) 2 which done by tuning 81,6 so that ,ss.. S (hence the multiplicative inside of F-1).
We thus obtain that
S 0 k 2 $1. + Ev, S 2PF Yo
ke + p
which finally leads
Ea, S F3 Fm+ (1 Fs) V F 7s if 20
(11)
k k
We now proceed to lower bound Ev.s, using again Equation the upper bound, for the case 2, 0 we can write that
10p. The proof is similar to the proof of
Ze 2 0 Eo,s 5 E,, I F. Entp(1
+ 2x)
((1 + (11+2)) 2t - 1)
I Fnt + 7/s)
m-p-1 7s
k +
stp-i pn+ Y 2
+++ p
using the concavity of r + (1 + x)) hiv and that % S 1. Then, for the case 2, I 0 we use that
2, S -o,,- < E S pm+p-1 F.,) (1 2x) k+p
s Em+t-1 (1 F.)) [ (1 7/) a+p-1
If n-tp-1 k+p
2 we furthermore obtain that (1 - 7/5) +1x
pmp--
(1 - 73)2 1 2% so
2, 50 Et S 24 2n. Fs).
Combining these results, we can lower bound Eg,. as follows,
2 Yo patp
E,. 2
27,
Fs)
(12)
k k+p
where the terms involved in this lower bound are analogous to the terms used in the upper bound up some multiplicative constants.
Summary: bounds on E We start with the lower bound. Using Equation 12
we obtain that
D
2
ktp To putp 2y,
pmtp-1 Fs)
++p p
3 log (2) mi
n
2 kipp11
k+p
F.
h+p
n
D-1
2F -tp-1--
61%
(1
F.)
D
k p
D
$=$1.
21

---

The first be trivially upper bounded by 2 Kty restrictive assumptions on P. For the second term, we use that k + S / [n + p) to exhibit the
E+p' which cannot be refined without more
reward function associated with a number of players n' == n 2(++p) size p' ==
n(k+p) # and competition of
pkkppi 2 P. 2(n+p) 1
1 D-1
Fs Ki F2) n x
a+p -
Σ
pn'tp'-1 Fe)
D $
D
SEA1A
F(x)
n+p-1
(1 (=x))) D
x ni { F(x)"(t'' Fxx))dx + n
n2'
D
n' + p'
D n+p
k+p
where we used that the reward is smaller than the probability that the coalition wins the auction. which is easily generalized even if i/2 is not integer.
We thus conclude the proof of the lower bound by writing that
(k+p) neo 2 (2(((()
n
12
T2 x
3 log (
+
+
X
(13)
2D
k
my
where the worst scaling for the left-hand term in the maximum is attained in k + p 3 u and provide 2. while for the right-hand term it achieved in k
n+p-1 and provides I+
As we already discussed, the upper bound can be expressed very similarly, remarking that the bound involving the terms 7a/i have to be divided by two, and the other term have to be multiplied by 3/2. We hence directly obtain that
(k p)) nEu so (0((((tp))(
n
+ n 2D
n 3(k: + p)
3 log (3) mk
+
x
(14)
Bounds on & We start by upper bounding the second sum by Under we hence obtain that ((ttp)
nē
D
kEL
72 D
1og(2/0)
RPP
8
mi
kEl:
1 1
log(2/8)
kip
< n 11,k - To.k +
my
which has a worst possible power of 2/3 when my 2 8lg((/68), corresponding to k + (n + 1). Replacing Ti,k by its expression, we further obtain that
=
nē < (8 log(2/0)
m+p-1
[llog (2) my
E+P
8 mi
F-1
IA
F-1
mg
(15)
For the lower bound on nET, we apply the exact same steps, remarking that the constant the very first step be replaced by since we Furthermore, we have to remove the term Lo,k- We finally obtain
the exact value of Ek+p in the upper bound.
log(2/0)
KTP
4log
n 2 -n
x
F-1
iΛ
+
(16)
me
D
22

---

Summary: bounds on (n) We conclude this proof by summarizing the results, and exhibiting the constants introduced in the theorem. First, by combining (T3) and (16) we obtain the following lower bound,
n - (1
mdp-1
4log (3) mi
(a(n) 2 r(n)
x
F-1 1A
+
D
D
+ ( 2
log ( m.
n
htp-1
+
x
(ks
2D
k +
Then, by combining 14 and (15) we obtain the following upper bound,
3 log (3) mi
Fa(n) S r(() +
+ 6 D
n
+
n2
2(n p)
(1: +p)
2D
3(k:
p)
+ n 8 log(2/6)
=+p-1 *4
4 log (2)
5
1
F-1
1A
F
mKk
mg
m
As a final step, we recall that this proof 5 is the confidence level the point estimate in each of the D points (O.....) DD-1...D-1) 1) and 11.k- Hence, obtain confidence 5 on the full estimate
(n) we need to multiply 5 by (D + 1) in the bounds presented above. As final step, we choose becomes a second order term in the bounds.
D ++1 = [ so that the term B I ViRu
After replacing and D by the appropriate values, we hence obtain that
2mn 8
log [[
log
(2(n) 2 r(n)
Pk,m
72 X SK.n.F
(17)
mm
m7k
m
with
ST, = 4V3 {
-
n
2 2[[nvmx 1))
n
1+p--1 klx
2nn p) - (k+p) +
+
2
and
k
u K+F
(log (2)
1
1^
+
(18)
mR
[n/mm
-
Symmetrically, we obtain that
n-p-1
log 22nmmmm]
log
[[my/m=]
ktp
Pa(n)) S r(n) +
knn
+ n x Sk..n.F
(19)
mmk
mi
my
with
8t = 6V3
72
+
n
and
2(n p) (k
2( [[[n mk
1)
3(k: p)
utp-1 ktr
F-1 1^
log (2)
E+r
F-1
8
FFP
1
Sk,,r
mi
m
[n m
mg
(20)
23

---

Hence, we obtain the statement of 7 by choosing Pk,, = Pk,n V Pk,n and fk.n,F Sk,n. V Sk,,,F Furthermore, it clear from their expression and the constraint constants are bounded by by absolute constants. Their expression provided in the theorem comes from choosing worst admissible value of for each of their components. This concludes the proof of the theorem.
p E 2-2 .333 3 that these two
Remark 2 (Improved constants for practical implementations). We can further improve the constants of the bounds according the position of with respect +
In Equation (upper bound): the constant 3 can be improved to 1 1ifi i 2 + while the constant 2 can be improved to p-p-1 if S n
Equation (lower bound); the constant on the right-hand side can be improved to
if +
These improved constants translate easily to the upper and lower bounds presented in and 14
B.3 Proof of Lemma 3
In this part, we prove the tighter confidence bounds, assuming that the quantile function of the value distribution is Lipschitz.
Lemma 3 (Improved bound for Lipschitz quantile function), Assume that l E V(n) and F-1 is L-Lipschitz, then there exists an absolute constant such that with probability 1- 8 it holds that
ale
log 2 /y/m
(4[n/me))
log
2[ny/ma
E+p
(n) -r()) S Bk
+ EL
m
171
Proof. As the result indicates, the improvement comes from providing finer upper and lower bound on the term nε, in the proof of Theorem We can start the refined analysis from Equations (T6) and
15
Let consider first the upper bound. In that case, the main ingredient comes from refining the upper bound of the difference T1,6 -0, To do that, we first provide an upper bound on A
4 (3)
k4
E+P We recall that, as in the previous proof, this should be multiplied by
[n/mml at the end the computation. We omit this term for now for simplicity. We consider a first case where the first term is equal to 1, which leads to
5
F
= =1-e e Z.D log( m
1
m7k
1
mi
log
1:
8
1
(4log(2/6)
<
log
k + p
6
1
}
2
2
x log
+ log log
1: +
5
For the alternative case we obtain a similar result,
(olo (3) m4
(8)
rtr
8
+
(lo (3) my
RtP
(1-
8
x-P
1lo((2/0)
m
4 log (2) mi
1
4
2 55
}
X
x
log
+ log log
1: + p
24

---

so the two upper bounds simplify to Next, we use the assumption that F-1 is L- L-Lipschitz to obtain that
4 log (
(
1
2
log
+ log log
m
k +
4 log (2) mh
WFF
( (
x+F
n( z0,k) = n F-1
1
F-1
Ln
4
log
+ log log
1: +
Ln
$ + p
x log
By substituting by 8/([n)mm)
we obtain that the linear dependency in n obtained with the for the upper bound, which matches the result at this [<[n/mp
previous analysis is refined to log point.
We now consider the lower bound, and work on refining the upper bound of the term - 1 in the
proof of Theorem To do that, we consider a new intermediary point =0 = F-1
For the rest of the proof we get back to the discretized formulation of the error (with generic step D-1), and upper bound
EE
S
Y2
F
71
Fn-p-1
D
D
keh
kE
nE
We remark that we can use the upper bound provided for n( To, ) upper bound nē), obtaining the result up additional steps are needed. However, we will simply use the exact same trick as before: we consider another sub-interval I22 for which this time it holds that l E 1/2 pk-p
multiplicative constants. Hence, it remains to upper bound E for which
Then, we
have that
n
Σ
Fp+
7
Σ
pntp-1
D KE
D
RE
mly-1
mip-
n
n D
Σ
8
D
mg
mg
kET
kET
ntp-1
n-p-1 ktp
12
8
122
8
mi
D
Just as before, we show that precisely, we obtain that
[Lol-148
cannot be too large if the quantile function is Lipschitz. More 1>
xiP
log(n) + p
m&
myn -+p-T
m&
1
so that we can finally write that
atp-1 E+r
ntp-1 2+p
8
R+P
log(n)
<
+
x
X
x L +
x
mi
n + p
D
mrk
log(n)
+ n X
X L
x
m
11 n
n
m
25

---

which is sufficient to conclude, since the multiplicative constants to mg "Mr
are clearly dominated
mmp
by log
B.4 Empirical UCB and LCB
The UCB and LCB in Equation 17) and Equation (19) depend explicitly on the unknown F via Fk,, and FF and therefore cannot be used in the implementation of GG.
Below, we give empirical UCB (Ü&(n,8)) and LCB (Za(n, 8)) by replacing St,,, and Sk,nr by empirical estimates ét and E
2[ /man
log [2[n
log
=2(m,,)=FP((0 (n((n) + 1 VinE
+
PE,m
+ n x Ek.
(21)
mk
m.
mip-1
log
P[nymal 8
log
2[ny/mm
k-p
(n) - (n () =
my T2 X Skin
(22)
mm
where Bk.n and ot. are defined in Equation
18
and Equation
20 and
dxtp +
pmp-1 SR,
[n/max
dk+p +
Z+ Sk
= 8 --p-1
n m
for
l m 1/6)
dx+p= = infid tO...., [n 11, pktp 2
m&
if the infimum exists and de-pp = otherwise.
It is corollary of Theorem I that (n) and (x) are indeed high probability upper and lower bounds of the true reward:
Corollary (Explicit upper and lower bounds). It holds that
P(LL((n, 8) & r(n) & Ün 8)) 21-
With D [n//me] and 11,k F-1 1 1 4 log 2[n
Proof.
the good event de-
mi
fined in Equation p iimplies that with probability
- 8 the following event H holds:
log
2 mmn
H vk S [
Pk-D S
Under H. and since by definition
fK+P > dxir
8
/8)
it holds that
me
4 log [2[n//ma)
detp D
x1.b F-1 1A
mi
This implies that ET,, 2 f and Et, 2 St. Therefore, we can incorporate in the proof of Theorem I the fact that the good event & implies Er. 2 Sk and Et 2 ft, F and obtain the stated result.
26

---

C Regret analysis of Local-Greedy and Greedy-Grid
C.1 Clarification on the feedback received by the algorithms
In this section, we consider the case where a feedback (in the form of sample from power of F) gathered only when auction is won. If this is not the case, the decision-man makerr only knows that the coalition lost the auction. Therefore, is lost, it makes sense to continue assigning n, agents to the auction time + 1. in order to gather the information that the algorithm wanted to obtain. The meta algorithm called CoMAB for coalition bandits described in Algorithm implements this strategy.
time é, ne agents are assigned to an auction and the auction
Algorithm 3 CoMAB
Init: To = Ø, m
Input: Algo
for t = 1...To do
if and auction at t 1 is not then
L Play n4 = 14-1;
Play same arm until an auction is won
else
Play Algo(Jm-1)
When auction is won play prescribed by input
Algo
if Auction is then
Observe Wn, sample from puttp Set Jm Jm-1 U {(wn: ne, m))
Record feedback obtained when winning
Update m m +1
Local-Greed, and Streedy-Grid then defined CoMAB applied on Tue and Toa for local greedy and greedy-grid respectively. These policies associate a play nm to an history Jm-1- In Algorithm and Algorithm the policies called sequentially T times and feedback is observed after each request. This gives an implicit definition of the policies.
Lemma 6 expresses the regret of CoMAB in function of the behavior of any policy when feedback observed after each request.
Lemma 6 (Regret of CoMAB). Consider policy n that associate to every Jm-1 play whe Define To = 2 and Jm = Jm-1 U [Wan, nm, m where w is a sample from a distribution with c.d.f F +P and n,, = (IIm-1). Consider m (m) the number of times a returns after m calls of a. After T iterations, CoMAB based has regret:
N
Rr < n=1
Σ Blm
p p+n (r(n") - r(m))
Proof. Call n, the play chosen by CoMAB at time
?t The auction is won time f}.
m. (1) = 10 S 1, n, n and 7 =1}
the number of times that is played and the auction is won up to time t and
Zn (1) Hp 1, and < (p) < 1}}
the number of times that n has been played between the m-th time won an auction and the m 1-th time. Note that (t) < m. (t) since at time t, π has been called most t times.
27

---

The regret of CoMAB satisfies:
T
Rr
Blr(n" - r(m))]
E
1 [i n}
(r(n") r(n))
N
(2)
E
mm (T)
(r(n') r(n))
Mrr (T)
E
Znnm (T)
(r(n')-r(r)) rr(n))
m=1
Σ Elm (T) p n
(r(n")-r(n) r(n))
where in the second last inequality, we used the independence between n, = n and (n) (T) ny depends only on the history at times t mm(n) while Zm.m (T) depends only on times t 2 (n).
C.2 Auxiliary result
Before proving the theorems, we present an auxiliary result from [6] that we to derive upper bounds that can be recovered explicit in the proof of the theorems. Since the proof is simple, we recall it for completeness.
Lemma (Lemma 4 from 6 For any Ç 2 1, the mapping
fc x E [(< + 2)$ v 3, oc) + sup IIEN
t S x
log(t)s
satisfies
f((x) S (S+2) log(z)5x.
Proof. We start by remarking that the function g(x) Tog(ay: is strictly increasing for all 2 es. Now, consider value Ax log(z)5 for some A > 0, such that 2 3 eS, By the monotonicity of eJo we have that
A Alo((r)
t> 888- - (log(t)< (log(s)< x x
(log(A) A) + log(x:) <log(log(z)))
Then, for A > 3, holds that log(A) + log(z) (lg((og(z)) (S 2) log(z)), so we can
simply choose A = (C + 2) to obtain the result.
All that is left is to verify that for this choice, s s= (C + 2)5 x log(z) 2 3 V e5, but this clearly holds for all > and 0.
C.3 Proof of Theorem
Theorem 2 (Regret bound for Local- Local-Greedy). Let A = min 1) (worst local gap). Under Assumption 2 and with a = (logs/2 + 1)-1, the regret of LG is upper bounded by problem-dependent constant: there exists (CM)NE(NTMY each satisfying C, ÖN ( ((x), such that Rr < Ene[N]ar Cn.
Additionally, the arm set forms a single estimation neighborhood, that is Vn E [M]: V(n) U [N], then each constant Cn can be refined to Ön (A,)),, providing Rx = Ö(VNT, which holds even when the reward function is not unimodal.
28

---

Proof. First, we denote by (n) the reward estimate used for arm n at time t, and by ( when the arm used to compute the estimate is fixed k E V(n). The proofs rely on concentration bounds on (z( derived from Theorem [ with confidence level 6, that will be fixed later. However, we will use this result with extra care given that the identity of the arm k used to compute the estimate is random variable, as well as its sample size (t). This issue is tackled with appropriate union bounds. Furthermore, in order to simplify the presentation we denote by {m, 6) the maximal diameter (as function of k)) of the confidence interval provided by Equation 77, defined by number of plays yn the arm used to estimate, and by a confidence level 6. More precisely, with notation of Theorem for any (k: n) [N]? least 1 oz Furthermore, [mm (t), 5τ) is increasing in 6, and decreasing in (t).). Finally, we use the notation K [loga/2(X)]] so that K+1'
(n) its value
write that (n), r(n)] I Emm (t), 6t) with probability at
We now prove the first statement of the theorem, by upper bounding the number of plays of each sub-optimal arm.
Single neighborhood Consider any sub-optimal arm n. The main ingredient of the proof is to tackle the forced sampling by using that if is pulled at time I, then it is either pulled "on purpose" or due forced sampling. However, it it forced sampled then must have been selected "on purpose" by being the best empirical arm in the neighborhood at some previous point in time. We hence consider the following good event
G. = (V' E {t- Lat],, [oot]....,f) f), (Vk V(n): mx(s) at), (N), - r(n)) S {(mx(s),
Using Theorem 1 bound on the values of l and m& (l) (1 could be replaced by ( [ox]()). Using this result, we first upper bound the number of plays of n up to horizon 7 as follows,
G. holds with probability at least - [ where we used a crude union
E
Σ
(m+ m}
SE E
1 13
(t Lot lott,....,01 0): Fa(m) 2 Fs(nn))
< E
Σ (3s (t [ot]..... .): Pa(n) 2 p,(n))) 1(9,}
+ +E P(G.).
As discussed above, the second term satisfies ET, P(G.) S Σta [t)) In order to make it constant, we choose 6, Piaeer For the first term, we use that Vs [al, (], (m) s ((a(1 att, 5.) and that n can be played only if the two confidence intervals overlap. Hence, we further obtain that
T
E
Σ fm. n)
E
Σ
1 (28(a(1-a)) An)
+ 1=1
(mn)
+oc
E
I (28(a(1 a)t, 2 Am))
Σ
(1 a²)
-
1=1
n²
ta.n
6(1 az4
n²
( +
1 K
1 since
lan
K +
and for a deterministic constant fa.m defined by
ta = supft E N 28(a(1 a)t, 81) 2 A
We recall that K = [loga/2 (N) is used to simplify the notation. The last step consists in upper bounding the value of tamn explicitly according and An. Considering some t 2 4 4V n + 1, from
29

---

Theorem
we know that there exist universal constants 3 and &, and we obtain that
2[ (e))
log 2 (2nn/ma (e))
)
$
log
6.
5x
E(a(1 o0), s 8
+ #XXE
ms(s)
mx(s)
log (2 + 1])((((1))
log (21 + 1)V(((()))
$ 81
+ x
a(1 a.)
a01 a)t
log (t9 (n + 1)))
log (t + 1)2)
$ 18
+
a(1 - (f)
a(1 - ai)t
7 7lgg (t)
7log (t) a(1 a)t
S 8
+ x
a(l a)t
Since a K+I it holds that a(1 a) K+I K+I
K 2 2[+IJ)
We then get that for some universal
constants 3' and g', it first holds that:
log(t)
E(a(1 - att, S
n(K + +))
V
(23)
where we bounded
log(t)
by
log(t)
Without this simplification, we also obtain that
log(t)
1 g¹
log(t)
a)t, S (K + +1}
8 +
(24)
The different scaling proposed in the theorem then come from using Lemma on 23 and (24). taking the minimum between the two (since both bounds are valid simultaneously), and for the latter splitting cases depending on Togtz) S ne being satisfied or not (taking this time the maximum between the two cases).
We provide the right-hand term of the result using
23 applying Lemma 7 with Ç = 1 and
4
(B
m( + +1)$g'
A
which leads to ta.n I 3r log(z). This provides the term O
of the result, and constants in the logarithmic terms can be recovered explicitly by recovering the values of 3' and g'.
n² Aズ
We then obtain the left-hand term of the result by considering log(t) < 1 for t Z 18n log(n) (first bound). Still using Lemma this simplification permits
Lemma first provides that
use and the threshold
(B (K (K
y
AZ R
and upper bound of fa.n 3y log(y), but only if this term larger than 18n log(n). This provides the remaining terms of the bound, and again the logarithms can be easily recovered by computing 3 and L'.
This concludes the proof for the moblemmddepeddee in the favorable case where all arms are neighbors, remarking that these upper bounds just have be multiplied by A,, and summed over [M] to convert into the regret bound. Furthermore, the moublem-iddeperann taking the minimum between the bound and A, remarking that the worst case A, = T omit the logarithms.
guarantee can be derived from
30

---

General case We now provide the regret bound for the general case, where at least some arms do not include [N] in their neighborhood. We recall that two main ingredients of Local- noel-Greedy are (1) that the arm n, played in /. is the best empirical arm in the neighborhood of (m 1) according to the simple estimates computed with samples from 74-1, and (2) that ny = 74-1 if m (1) < at (forced sampling). Hence, similarly to the previous proof we use that n, is either pulled thanks to a "greedy play" or because of forced sampling. Furthermore, the two cases can be merged because forced sampling can only come after n, being pulled because of a greedy play in the recent rounds. More precisely, we use that
{rg = n) C Es E [t - LLat]] : n, = (e,) 2 [as
(25)
This argument is at the core of our analysis, but before going further we need to introduce the notion of locally optimal plays.
Definition 2 (Locally optimal plays and optimal path). Given reference arm E, playing E V(E) is locally optimal if = argmaxeev(e) rk)). In that case, n is the best neighbor of E, and we use the notation n = (m).
Furthermore, a sequence of successive locally optimal plays is an optimal path towards n². By construction of an optimal path contains at most K = (log((N) sub-optimal arms.
The last fact presented in the definition is trivial: in the worst case the path start at one of the extremes of the interval [N] and n² the other. By design of V (Definition Dp we obtain that n² is reached in [logs/2 (Nv) steps at most. The rest of the proof is based on the idea that, when t is large enough, the algorithm starts following an optimal path with high probability, so a sub-optimal arm can be optimal path from another sub-optimal arm to n². We formalize it
played only if it is located
with the following result.
Lemma 8 (Existence of "recent" sub-optimal play). For any time step E [T] and arm + n², it holds that
{m== =n= n) A. = (3s E [[1 a1 1, LE .. E V(): F,() S FF((), m1(1) 2 a(1 - a) and r(1) > r(()),
Proof. Starting from 25 we first use that either n j xt (E.), and in that case playing n is locally sub-optimal so this event belongs to A,. or = v² (f.). Let us now consider this second case: by definition of the leader, f, was played right before the sequence of forced plays of started, which must have happened at least as recently as - aat] - 1. From that point, the recursion pattern is clear: l, must have been selected in the last (a(s 1)J. by either being a locally sub-optimal play or not. The first case is included in Ar, why the second requires to add another step in the analysis. Furthermore, the arm used to estimate lg was itself samples at least proportionally to s. Using that this can happen K times, and that the worst number of steps to look into the past at each step is at most a fraction (1 - ax) of the number in the previous step, we finally obtain that there have been a sub-optimal greedy play in the last [[1 - a) K t, t) steps.
Before going further, we justify the tuning a = I later in the proof). At this step, we can simplify the notation by remarking that
k+ by stating that maximizes a<1 - ox (used
K
K
(1 (1-a)*=
20-1
K
+1
hence we replace (1 a by e1 in the rest of the proof.
In words Lemma 8 states that, even if forced sampling slows down the ascension towards n", since optimal paths contain at most K sub-optimal arm then n" relatively fast to reach from any arm in [N]. Next, we use this result in the regret analysis by considering its occurrences with the following event,
Hr = (Vs [e 16,, Vn E [N], Ak E V(n) mx()) 2 1 K
(n) r(n)) < {(mp(s),
31

---

Then, for any tx E N we can upper bound the number of plays of each sub-optime arm n E [N] as follows.
T
Σ
1 (n+ = n}
SE
Σ 1(
121
$ sk + E
Σ 12tx
[AA,
Hi)
+ Σ P(H.).
12tK
with the slight abuse of notation that now defined with coalition size N and not the local value of n considered. The rest of the proof is analogous to the simple case, where all arms are in single
neighborhood. We first choose òz Noत.. and obtain that Eisex IPHH)) - E بي سह
Next, we tune x large enough so that Eiiii 1(,, H.] - 0. This can done by choosing
lx = sup { 1 E N: 28
( e- (1+ s
where A = min,e(N--j((fff + rn)))
We then deduce the result by applying the exact same steps as for the upper bound of la by carefully replacing 6, Vi by 6 'o and a<1 ajf by r Lemma then allows to easily obtain the desired scaling, and to make the upper bound explicit by substitution. Since K is logarithmic in N, it clear that only contributes to the bound only by logarithmic factors.
C.4 Proof of Theorem
Theorem (Regret upper bound for Greedy-Grid), Suppose that GG is tuned with confidence level Noy and a = 1/4. Then, for any T N holds that
RΙ = ŌŌ
Σ
1
log(T) An
Ad
[nn<n"]
1fn n²) (m>>n?))
(x(n") 1
An
A2
A
AEE
nES
((((n)
Additionally, holds that RT
(V BBI)TT
for K [logs/2 (N)J-
Proof. As the theorem suggests, we will use different arguments depending on the position of n with respect the grid and the optimal bin B Before that, we introduce the crucial result of this proof: for each time large enough, thanks to the design of Greedy-Grid, all arms in optimal bin 5 are estimated with a simple estimate computed with a linear number of samples in
Following the implementation GG, at each time and for each arm n E [N], a confidence interval [LCB, (n), UCB, (n)) is computed so that r(n) [LCB, UCB, (n)] with probability at least d,. Similarly to the proof of Theorem 2 we consider a "good event" stating that all confidence intervals where valid given time range before I,
Gi -
vs
31
t
Vn E [N], (e()) E [LCB, UCB
16
It is clear that Σ P(G)) S Σta 2 2t 7 where the second union bound on N comes from considering the (random) identity of the arm whose samples are used to compute the interval. The following results proves that, under Gr, there is at least one arm in the bin B² that was played linear number of times in t.
Lemma 9 (Linear number of plays in B* under Ge). Under Gr there exists an arm E B* U {uf (n*), of (r(*) satisfying m. (3t/4) 2 + $. where we call K K= K = [
TK
Proof. Ge guarantees that any play during the interval sampling), were decided with valid confidence intervals. Indeed, starting at 3t
[[]].]] (including those due to forced
sure that all
16
32

---

forced exploration launched before that time is completed in t/4. Furthermore, it is also direct from the design of the algorithmss that, if rs (n) E [LCB, (n), (n)) and Greedy- Soridy--ridd not forced to sample the previous arm it must hold that (1) it is playing the grid, (2) it is playing an arm in B*. Indeed, no arm from sub-optimal bin would eliminate its best neighbor.
We consider two cases. First, if an arm nt E B was played between rounds [ and [ In that case it has collected at least & samples before t, thanks to forced sampling. In the alternative case, the grid was played between those these two rounds, which incurs f plays of argmax r(s) since by 9, argmax r(s) not eliminated when the grid played. Then, notice that argmax, r(s) C
'f
{n", oo (n*), ), o )] The result follows by combining the two cases.
Without loss of generality, we assume in the following that K 2 2 (if this is not the case, just replace
K by max(K, (K 2)). As direct consequence of Lemma 9 using Theorem I Jnder G. there exists some constant 3 and & (coming from the bounds of the theorem multiplied by 2 = 4) such that the LCB of arm n²* satisfies
log
2[Nv[]
log
2[Nv[]
3/
Vs
LCB,(n") 2 r((*))
B
K
N X
K
4
t
(26)
To simplify the notation, denote the right-hand term by E(t in the rest of the proof. Using this result, we can now consider all the sub-cases presented in the theorem. We fix a sub-optimal arm
n. and upper bound Σ 1 {n, n. Ge depending on the position of n with respect to the grid S. Similarly to what we did in the proof of Theorem 2 we relate the pulls due forced sampling to actual decisions by stating that, if ne = then there exists a round s between - [t/4] and t such that GG requested a pull of arm n from a "grid play" or a "greedy play".
Case 1: n E S. In that case if n is pulled then, since there is no forced sampling for the arms of the grid it directly holds that
(n) Z max LCB,(n') 2 (CB. 2 r(n") E(L)
(27)
n'E[N]
On the other hand, under G. it holds that
log (2[NVE)
log 2[[VV] 6,
UCB+(n) S r(n)+ + B K
N NX
K
mm(()
min (1)
(t)
so pulling arm is possible only if E(t) + E'(t, m,((t) An, that we simplify to 28' (t, m. (f)) > A, or (t) 2 An- Considering the second term leads constant problem-dependen bound, analogous to fa.n in the proof of Theorem 2 Hence, we focus on the first term, that provide the log(T)) bound.
This time, we don't know if mn.()) is large or not. This explains why we obtain a UCB-like (o(logTT)) upper bound with this technique. We use that
[[N de
2[NVV]] ôT
t T = log
< log
T
(log(TT)
Then, similarly proof of Theorem m., (t) = (6) then
mitigate the asymptotic scaling in N by noticing that if N simplifies. In that case, we obtain a sub-Gaussian confidence interval,
(1)6
and similarly to the analysis of UCB 3 we obtain that arm n is only pulled at most δ ( (log(T) N6
Ag
times with high probability. This is the first part of the result for S.
33

---

We then use another analysis to derive the constant problem-dependent bound. We remark that, when the confidence intervals are valid, the best arm between oz (n²) and (n²) can only be eliminated by an arm 8 E B². By design of the algorithm (exploiting the unimodality assumption), it furthermore holds that it E B and those two arms are eliminated then does not play on the grid. Hence, the constant bound in this case comes from upper bounding the time required for this event to happen under Gt. If off (n*) not eliminated it must hold that UCB, (n*)) 2 LCB,(n") (if n I n*). Furthermore, Lemma also guarantees that
UCB((ve(n")) & r(ve(n")) E(t),
therefore the event that vy(n") is not eliminated is only possible if (t) > A (n-) We can then
Lemma 7 following the same in the proof of Theorem righht after (33 and 12
When T is large
enough, the derivation provides the scaling Ö
We can then can follow the same steps for
AZ of (m*)
vf (n²), and obtain ① up
Furthermore, it clear by analogy with the proof of Theorem
that for small values of T the upper bounds have be multiplied by a N²2 factor. Finally, we can remark that if n < n² the first bound is used, while the second is used for n > n². This concludes the derivation of the upper bound for S.
Case 2: n & S, (n) * B We prove that this case is actually impossible under the good event, which explains the surprising constant upper bound independent of any gap. Indeed, if & S is played, then must hold that its right and left neighbors the grid are eliminated. Since B(n) * B then at least of them has reward at least good any arm in B(n). However, if playing arm was possible under Ge it would hold that
38 B(n)
r(t) (C)
> max (UCB, (vy (n)). (U (n)))
2 max(r(vp (n), r( (n))) 2 r(f):
which is contradiction due the strict inequality in the second line. Hence, the number of time such arm n is played simply upper bounded by Σ P(G.), which is (by design) bounded by universal constant.
Case 3: & S, B(n) B* We use that n, implies that n, due greedy play some round E (3t/4, f). Under Gr. we can thus directly use (26). and obtain that if 2E I A this event is not possible anymore. Using the same derivation in the other cases (involving Lemma 7),
obtain the upper bound scaling in O [ for T large enough, and by O
N2
in general.
AZ
C.5 Regret of Greedy-Grrd adapted for non-unimodal rewards
In this section we develop the result presented Section regarding the adaptation of Greedy-Gris -rieddd-rriia in the case when the reward function is no longer assumed to be unimodal. We recall that the adaptation consists simplifying the definition of the set C, in Algorithm by
C. E S. L
We call the resulting algorithm GG-NU, for Greedy Non Unimodal, to differentiate from the original version of GG introduced in the paper. In the following, we formalize the upper bound of the regret of GG-NU, and discuss how this result is obtained by adapting the proof of Theorem 3 from the previous section.
Theorem 4 (Regret of GG-NU). Suppose that GG is tuned with confidence level 5 Naga and 1/4. Then, for any E N holds that
log(T)
Rr Ö5
Σ
InBB
Additionally, holds that Rr δ (V(K + IB+ITT) for K [log3,2 (N)J.
34

---

Proof. The proof follows the exact same steps the proof of Theorem To adapt the arguments GG-NU, we first remark that it suffices identify which part the proof uses the definition of the set C.. We then find that this is the case when analyzing the Case / in the proof, namely the regret caused by sub-optimal arms in the grid |S]. More precisely, to obtain the bound of Theorem 3 for GG we provide two simultaneously valid upper bounds: logarithmic (log(T))) upper bound with a reasoning akin to the standard UCB analysis, and then a constant upper bound that carefully leverages the definition of C. We easily verify that the steps for the logarithmic bound remain valid with the new definition of C.. while the second bound clearly does not hold. This completes the adaptation of Theorem 3 (for GG) into Theorem 4 (for GG-NU).
3 presented in Appendix C.4
D Experiments
All the code for the experiments is written in Python. We use Matplotlib for plotting [18. Numpy 15 for numerical computing and Scipy [3I] for scientific and technical computing. Seipy and Numpy are distributed under the BSD 3-Clause, and Matplotlib is distribution under BSD-style license. Theses licenses allow free use, modification, and distribution of the library. All the experiments were conducted on single standard laptop, with an execution time shorter than 24 hours.
In a first simulation, we consider a coalition of size N 100 and a competition of size p 4. At each timestep f, the algorithm decide number of bidders n, to send to the auction and the values of all bidders (coalition and competition) v E {0, 1) | are sampled according B(0.05). With octp' the reward V(I) V(2) is received and V(I) is observed. The (pseudo) regret at time t is then computed as the sum of reward obtained up to time t. The simulation above is repeated 20 times with random seeds and the mean value across seeds reported as the expected regret (R(). in Figure 3 Error bars represent the first and the last decile.
probability nt
In this simulation, the parameters are chosen to allow for having a significant number of players while keeping a gap A large enough (about 2 x 10-9) to be able to observe logarithmic regrets for the baselines. LG practically outperforms other approaches by a large gap. The two algorithms that ignore the structure (UCB and EXP3) end up exhibiting a worse regret than LG, OSUB and GG, which expected. However GG has a much higher regret than LG and only outperform UCB and EXP3 for horizons greater than 10S, when it starts to climinate points from the logarithmic grid S. Indeed, due to the explicit use of concentration bounds in the algorithm, which multiplicative constants are not optimized for practical implementations, GG does not practically reach the constant regret regime in the horizon of these simulations.
To illustrate the practical performance of LG, we perform additional simulations which are identical the first one except for the parameters N, p, and the distribution of value that are set according to Table 2 The results are plot in Figure 4 where it is shown that LG reaches the constant regret regime after only couple hundreds or thousands time steps while the other algorithms are still in the transient linear regime.
Table 2: Configuration of additional experiments presented in Figure
Position
N
p
Value distribution
A
Top
5
2
Beta(a = 0.35, b= 0.63)
5 X 10 10-5 5
Middle
Trunc. Exp(O,
4
10
10-4
Bottom
20
4
Trunc. 1x)
5
3 x 10
35

---

Expected Regret R(T)
UCB1
8000
Exp3
OSUB
6000
Local Greedy
Greedy Grid
4000
2000
50000
100000
150000
200000
Horizon T
Figure 3: An empirical illustration of T simulations in the following setting: values distributed according to B(0005), N = 100 and = 4. We benchmark LG and GG (this paper), OSUB [9) UCB 3 and EXP3 [4] in terms of R(T) computed over 20 trajectories. Error bars represent the first and last decile.
36

---

Expected Regret R(T)
UCB1
Exp3
OSUB
Local Greedy
Greedy Grid
0-
100
150
200
Horizon T
Expected Regret R(T)
UCBI
10
Exp3
OSUB
Local Greedy
Greedy Grid
4-
100
200
300
400
500
Horizon T
Expected Regret R(T)
25
UCBI
Exp3
OSUB
Local Greedy
Greedy Grid
15
10
0-
250
500
750
1000
1250
1500
Horizon T
Figure 4: Illustration of additional experiments. Details of parameters provided in Table
Complexity analysis The time-complexity of both GG and mainly comes from the computation
of reward estimates. They computed by replacing the integral in Equation 5 by Riemann
37

---

with VV terms (the reasoning behind the number of terms needed is the same as in the proof of Theorem Therefore, whenever reward estimates of neighborhood of size ((N) needed, costs ( (T) operations. Note that during forced exploration steps, reward estimates are not needed and therefore the associated cost is not paid. The total time complexity therefore depends on the number of times reward estimates are needed which itself depends on the trajectory. However, our algorithms could be modified to guarantee that reward estimates needed at most (log(T)), times for instance by only performing updates at the end phases of exponentially increasing length. This would lead to mean complexity per iteration of (NN log(T)), and similar theoretical guarantees by a slight adaptation of the analysis. This would reduce the burden of using of incorporating the structure in the algorithm, compared the ((N) cost of the baselines (which is even ((1) for OSUB).
E Broader Impact
The collection of user data should be carried out with the preservation user privacy in mind. This issue is at the forefront of recent, ongoing developments, such as the European Union's 's General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA).
In online advertising, maintaining privacy presents new challenges, as decisions must be made without complete access user data.
This paper tackles one such challenge by detailing Multi-Armed Bandit (MAB) algorithms that Demand Side Platforms (DSPs) in the repeated auction for placements, without the need for prior knowledge of each campaign's value. This study is therefore step towards the realization of practical user privacy. It is important to note that the assumptions we make require that the actions of the DSP have a limited impact on the market, which should be carefully verified in practical applications.
to determine the number of ad campaigns that should partake
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical and experimental results provided in (Theorems 1o and ap- pendix D correspond to the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the discussion the end of Section B and future work directions in
Section 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: In Theorems to 3 the assumptions are referenced in the statement of each theorem, sketch of proofs provided below each theorem and the detailed proofs available Appendices
and C.4 respectively.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Experiments are described in the text in Appendix D and can be reproduced using the code provided in supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: yes the paper provide open access the code (as zip folder in the supple- mentary materials) with all the instructions needed to reproduce it
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public//giide//Ddeeebbbisss wwt.aaabmiiiiooooooooooooooooiie for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips //iiss.c/pput cttp://cccpbblccgcuiceeeeeecc guides http://wwllllgliieeeoooeeuaaaaaa wwtp/oeeeiiiiiiinnnooooooooo Pollccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Yes all the details for the experimental setting are provided by the paper (see Appendix D)
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Error bars are reported and defined in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments were run on a laptop in less than a day (see also Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Yes the paper is conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[Yee Yes]
Justification:
The discussion on the Broader Impacts of this work is in Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
42

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The python packages were cited and open source licenses (see Ap- pendix D
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
43

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, batasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code for the experiments is provided in the supplementary materials zip folder.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
44

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "WTAwhNpEjs", "reviewer": "Reviewer_TZVE", "summary": "This paper studies repeated second-price auctions with ex-ante bidder coalition. There are two groups of bidders, one of size N and one of size p. At each period $t$, a decision maker can choose $n_t$ out of the N bidders to compete with the other p bidders in an auction. Crucially, the decision maker chooses the bidders without knowing their values (due to privacy concern). The decision maker aims to maximize the total expected reward (computed according to the second-price auction rule). This problem reduces to a multi-arm bandit problem with a structured reward function, where each possible number $1\\le n \\le N$ is an arm. The authors design two algorithms, Local-Greedy and Greedy-Grid, to solve this problem with constant-in-T problem-dependent regret and $\\sqrt T$ problem-independent regret. Techniques include a non-trivial concentration bound for the reward functions and adaptations of the unimodal bandit algorithm OSUB.", "questions": "(Q1) In addition to the maximum realized value, can the decision maker also observe the reward (maximum value - payment) when the auction is won? Line 44 says yes, but Line 62 says no. If the reward (equivalently, the second highest value) is also observed when the auction is won, can the results be improved?\n\n(Q2) Can the results be generalized to the case where the bidders' value distributions change over time (but the bidders are still symmetric within each period)?\n\n(Q3) What if bidders are asymmetric?  See (W2).", "limitations": "**Suggestions:**\n\n(1) Capitalize \"Coalition Gain\" in title.\n\n(2) Line 2: \"their values\"", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(S1) [Significance] This work is well motivated. It is motivated by: (1) The interesting observation that the demand-side-platforms (DSP) on online advertising auctions can coordinate the bidders to maximize the total gain; (2) Due to privacy concern, DSP can only choose coalition without seeing the bidders' values. In particular, (2) naturally turns the problem into a multi-armed-bandit problem with small arm space and structured reward function, which is an interesting connection.\n\n(S2) [Significance & Quality] The authors find algorithms that achieve problem-dependent regret bounds that are *independent of T*, which is a surprising result, especially when compared to the UCB1 algorithm with problem-dependent log(T) regret bounds. A problem-independent regret bound in the order of $O(\\sqrt{\\log N + |\\mathcal B^*|T})$ that is better than UCB1 and EXP3 is also given. These results are impressive and the underlying analysis are non-trivial.\n\n(S3) [Quality] Experiments are provided to validate the advantage of the proposed algorithms, which is good.\n\n(S4) [Clarify] The writing is very clear overall. While the full proofs of the results are involved, the authors nicely summarize the main ideas and discuss interesting aspects in the proofs, including potential improvements in the analysis. This is very good.\n\n(S5) [Significance] The proposed future directions are interesting, and can potentially lead to some follow-up works.", "weaknesses": "(W1) The assumption that the reward function $r$ is unimodal (Assumption 2) feels restricted. Although the authors briefly discuss how to handle non-unimodal functions in Line 311 - 313, no formal result is given.\n\n(W2) The assumption of symmetric bidders also feels restricted.  When bidders are asymmetric, the decision maker can choose either (1) a subset of bidders or (2) a uniformly random subset of n bidders from the set of N bidders to compete with the other p bidders in an auction.  Can the authors provide some discussions about asymmetric bidders?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and suggestions, as well as for appreciating the key contributions of our work. Regarding the unimodality assumption (W1), we answer in a general comment for all reviewers. Regarding the symmetry of bidders, see the paragraph (Q3) below.\n\n(Q1) We apologize for the inconsistency, we will correct line 44. Indeed, our analysis is conducted by assuming that only the maximum reward is observed. However, we could use the same procedure presented in Section 2.2 if the sequence of second prices (price paid by the winner) $\\\\overline{S}\\_{k} = (s\\_{k,1}, \\\\dots, s\\_{k, m_k})$ was observed instead of $\\\\overline{W}_k$. The cumulative distribution function of observations would become $G_k: x \\\\in [0,1] \\\\mapsto (k+p) F(x)^{k+p-1} - (k+p-1)F(x)^{k+p}$, and thus it is also possible to estimate any power $F^\\\\ell$ from $\\\\overline{S}_k$ via a suitable inversion formula. Furthermore, the same could be done if both first and second prices were observed, but the inversion would be more intricate because the joint distribution of $\\\\overline{W}_k$ and $\\\\overline{S}_k$ should be considered. This might allow a slight improvement of the multiplicative constants of the result, but probably at the cost of more intricate computation. We will add this discussion at the end of Section 2.2.\n\n\n(Q2) This question is indeed particularly relevant in real-world applications, thank you. First, the progressive change of distribution can imply a change in optimal arm, but also that previous observations progressively induce biased estimators. Hence, we believe that our algorithms might require some adaptation to tackle a non-stationary value distribution. Since our problem is framed as a structured MAB, it might be natural to look for inspiration in the rich literature on non-stationary MAB problems. In this literature, the general idea is to mitigate this bias by forgetting some of the past observations, either passively (with a sliding window or discount factor, see e.g. [1]) or actively (with change-point detectors, see e.g. [2]). \nThen, the analysis of the *dynamic regret* can be conducted by assuming a property of the non-stationarity, such as an upper bound on a number of changes or on the total amplitude of variations (we could imagine a budget on $\\sum_{t=1}^T ||F_t-F_{t+1}||_\\infty$ for instance). We believe that our algorithms can be adapted to include these ideas, and the practitioners' choice would certainly be to opt for a simple sliding window mechanism. We leave the formalization of this adaptation and its analysis for future work. We suspect that the structure of our problem might imply interesting non-trivial properties, for instance by making it easier to detect changes in the reward function because changes in $F$ can be detected when sampling any arm.\n\n\n(Q3) The assumption of symmetric bidders is commonly used in the auction\nliterature (see e.g chapter 2 of [3]) to build understanding of problems that couldn't be solved in the\nfull generality of arbitrary bidders. \n\nFollowing your comment in (W2), if we considered asymmetric bidder the action\nspace would include all possible combinations of players from the coalition,\nmaking the problem combinatorial. In addition, the estimation of the reward\nfunction with different value distributions becomes very intricate, so overall\nthis setting might be too difficult to actually exploit the structure of the\nproblem. \n\nWe believe that studying the symmetric case is a necessary step to unlock addressing more complex settings in future work, such as coalitions built out of several groups of similar bidders.\n\n\n[1] Garivier, Aurélien, and Eric Moulines. \"On upper-confidence bound policies for non-stationary bandit problems.\" arXiv preprint arXiv:0805.3415 (2008).\n\n[2] Besson, Lilian, et al. \"Efficient change-point detection for tackling piecewise-stationary bandits.\" Journal of Machine Learning Research 23.77 (2022): 1-40.\n\n[3] Krishna, Vijay. Auction theory. Academic press, 2009.", "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": "", "extra_scores": {}}, {"review_id": "YU8rINgnz1", "reviewer": "Reviewer_Ja3N", "summary": "This paper studies the problem of repeatedly selecting the number of agents to form a coalition against the environment to maximize the cumulative reward in second-price auctions. Specifically, the paper supposes that all bidders are identical with unknown value distribution $F$, and in each round $t$, $n_t$ bidders out of $N$ bidders would be chosen, and truthfully bid against $p$ bidders. The goal is to maximize the expected reward function $r(n_t)$. Under the assumption that $r(n)$ is an unimodal function of $n$, the paper first presents an estimation of $r$ via powers. Under this component, the paper presents two algorithms: Local-Greedy ($\\mathtt{LG}$) and Greedy-Grid ($\\mathtt{GG}$), which both utilize the segmentation structure of the estimation result given above. The difference is that Local-Greedy searches locally, while Greedy-Grid does an iterative elimination on segments. The regret of Local-Greedy is bounded by a problem-dependent constant, and the regret of greedy-grid is $\\tilde{O}(\\sqrt{T})$ (I am not sure if I am correct here).", "questions": "1. Can the authors provide intuitions on what will happen to the proposed algorithms when the function $r(n)$ is not unimodal? \n2. Is it prevalent that Greedy-Grid performs worse than OSUB in practice? Could the authors explain intuitively/theoretically why Local-Greedy works better than Greedy-Grid?", "limitations": "The authors have addressed the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem studied in this work is quite interesting and has some practical implications. I very much like the estimation result as given by the paper, which utilizes the structure of the problem well and provides strong insights for designing searching algorithms with low regret. I believe this is the major contribution of the work and is solid. In fact, with the sectioned structure of the estimation, the two proposed algorithms are natural (but not naive). Overall, the paper is also well written.", "weaknesses": "In my opinion, the major weakness of the work is that all the results are supported by the assumption that $r(n)$ is an unimodal function of $n$. In my intuition, when $r(n)$ is multi-modal, both proposed algorithms may stop searching in a sub-optimal peak. Please correct me if I misinterpret. I wonder if such a mis-stopping can be prevented by doing the search more \"patiently\". \n\nAlso, in the experiment part, it seems that the Local-Greedy algorithm always enjoys a better performance than Greedy-Grid, and Greedy-Grid seems to perform worse than OSUB. This makes the theoretical regret results of Greedy-Grid weaker.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review. First, regarding the last\nsentence of your summary, we want to precise that for Greedy-Grid (GG) the regret bound we\nobtain is **the minimum** between\n$\\sqrt{(\\log_2(N)+|\\mathcal{B^\\star}|)T}$ and a problem-dependent constant\n(independent of $T$). We answer your question about unimodality above, in a\ngeneral comment for all reviewers. Below, we answer your second question about\nthe comparison between the performance of Local-Greedy (LG)/OSUB and Greedy-Grid\n(GG).\n\nFirst, we refer to the discussion at the end of the paper (l.306-337) for a detailed comparison of the theoretical results obtained with our two algorithms. We recall that both algorithms admit constant problem-dependent regret (see Theorem 2 and 3), but the scaling of the constant is better for GG, and furthermore permits to derive $O(\\sqrt{T})$ problem-independent guarantees (which we cannot obtain for LG due to the *local* gap in the bound). Hence, from a theoretical perspective Greedy-Grid enjoys better guarantees than Local-Greedy. However, our experiments indeed show that Local-Greedy performs better in practice. In our opinion, there are several reasons that might explain this gap between theory and practice.\n\nA first reason is that the scaling in the worst local gap in the analysis of Local Greedy (Theorem 2) might be conservative: this gap can be paid in a scenario combining bad initialization (very far from the optimal arm and with flattest part of the reward function on the path towards the optimal neighborhood) and bad luck (a ''plausibly maximal'' number of steps is taken to move in the good direction). It is likely that in practice this scenario is quite rare, and thus not seen in our experiments. Although the analysis of LG might be made slightly less conservative (see l.322-327 for a discussion), it seems impossible to completely remove some local gaps from the analysis of Local-Greedy in the worst case.\n\nFurthermore, the analysis do not capture the fact that in some cases\nLocal-Greedy might also be lucky and start playing in the optimal neighborhood\nvery fast. On the other hand, this situation cannot happen for GG, which\nrequires enough statistical evidence to eliminate all sub-optimal neighborhoods.\nWhile this step in GG is the reason for its improved theoretical guarantees, it might have an empirical cost because GG is ``always cautious'' compared to LG. Lastly, we discuss l.334-337 that another reason for that practical gap might also be that implementing LG does not require to compute confidence intervals, contrarily to GG. Hence, it is possible that the confidence intervals of Theorem 1 can be tightened, which would directly benefit to the performance of Greedy-Grid by accelerating the search for the optimal neighborhood. We leave potential refinements of the bound presented in Theorem 1 for future work. Additionally, we believe that these intuitions also hold when comparing GG and OSUB, from which LG is strongly inspired. We believe that the comparison between LG and OSUB justifies the interest of our approach from a practical perspective. \n\nWe will complete the \"Experimental results\" paragraph l.338 with the parts of this discussion that are not already presented in the previous paragraph l.306-337, in order\nto provide more intuitions about why LG works better than GG in our\nexperiments.\nWe believe that analyzing those two algorithms in our paper provides a good\noverview of what is possible to achieve: GG has the most appealing theoretical\nguarantees but is outperformed by LG in our experiments, suggesting LG\nis a better choice in practice.\nWhether LG can be modified to achieve the theoretical guarantees we obtain\nfor GG is an interesting but\nchallenging open problem.", "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": "", "extra_scores": {}}, {"review_id": "kgLNcnHfTc", "reviewer": "Reviewer_RP8o", "summary": "The paper explores strategies for maximizing the cumulative reward in repeated second-price auctions, where agents draw their values from an unknown distribution. The problem is modeled as a multi-armed bandit (MAB) scenario with structured arms, where the decision-maker selects a subset of agents to compete in each auction to optimize the coalition's total gain. Two novel algorithms, Local-Greedy (LG) and Greedy-Grid (GG), are introduced, both achieving constant problem-dependent regret. LG, while practical and outperforming GG in experiments, avoids reliance on confidence intervals. GG, on the other hand, offers problem-independent guarantees and better theoretical performance. The paper also presents new concentration bounds and theoretical guarantees for these algorithms, positioning them as significant advancements in the field of online auction optimization using structured bandit approaches.", "questions": "1. Can you provide more details on why you chose to use synthetic data for your experiments? If you have plans to include real-world data in future work, could you outline how this might impact your findings?\n2. How sensitive are your algorithms (LG and GG) to the choice of parameters like the exploration parameter $\\alpha$ and the confidence levels $\\delta$? It would be helpful to understand the range of values for these parameters that ensure robust performance across different scenarios.\n3. The paper assumes unimodality of the reward function and i.i.d. bidder values. Can you provide more empirical or theoretical justification for these assumptions? Are there any real-world scenarios where these assumptions might not hold, and how would that impact your algorithms' performance?\n4. Could you provide a detailed analysis of the computational complexity of LG and GG? Specifically, how do these algorithms scale with an increasing number of bidders and auctions? Are there practical optimizations or approximations that could reduce the computational burden without significantly impacting performance?\n5. The paper focuses on second-price auctions. How would your algorithms need to be adapted for other types of auctions, such as first-price or generalized second-price auctions? Are there specific challenges or advantages in these other auction settings?\n6. The paper introduces new concentration bounds. Could you elaborate on the derivation of these bounds and how they compare to traditional Hoeffding bounds in practice? Are there specific scenarios where your bounds provide significant advantages?", "limitations": "The authors have provided a thorough theoretical foundation and practical implications for their algorithms, but there are areas where addressing limitations and potential societal impacts could be improved. They mention some limitations in their theoretical assumptions, such as the unimodality of the reward function and the i.i.d. nature of bidder values, but these could be more explicitly discussed in terms of their practical implications. For instance, real-world scenarios where these assumptions might not hold should be identified, and potential mitigation strategies should be outlined. Additionally, while the paper focuses on improving algorithmic performance, the broader societal impacts, such as how these algorithms might affect market fairness or competition in online advertising, are not discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a highly original approach to optimizing online auctions using structured bandits, specifically through the Local-Greedy (LG) and Greedy-Grid (GG) algorithms. This novel problem formulation merges auction theory with multi-armed bandit (MAB) frameworks, particularly for online display advertising. By focusing on bidder coalitions and the inherent structure of the reward function, the paper overcomes some limitations of previous work and offers a fresh perspective on auction optimization.\n\nThe theoretical contributions are substantial and well-supported. The authors rigorously derive regret bounds and introduce new concentration bounds crucial for performance guarantees. The detailed proofs and theoretical analysis in the appendices demonstrate the robustness of the methods, providing a solid foundation for understanding the algorithms' behavior under various conditions. This rigor ensures the results are both novel and reliable.\n\nThe paper's clarity is another strength. The authors explain complex concepts clearly and logically, progressing from problem formulation to algorithm development, theoretical analysis, and experimental validation. Key ideas and assumptions are stated clearly, and the algorithms are described in detail, making the methodology easy to follow. Illustrative examples and tables, like the comparison of regret guarantees, further enhance readability and understanding.\n\nThe work's significance is evident in its application to online auction optimization in online display advertising, a multi-billion-dollar industry. Improving auction algorithms can lead to significant economic benefits. By addressing privacy constraints and the need for efficient ad placement strategies, the proposed methods can greatly enhance the performance of demand-side platforms (DSPs) in real-world settings. The theoretical advancements also contribute to the broader field of MAB research, especially in structured and unimodal bandits.", "weaknesses": "One significant weakness of the paper is the limited experimental validation. The authors primarily use synthetic data, which does not fully demonstrate the practical applicability of the algorithms in real-world online auctions. To strengthen the practical relevance, the methods should be validated using actual auction data. Collaborating with industry partners or using publicly available datasets would improve the experimental section.\n\nAnother concern is the narrow comparison with existing methods. The paper compares LG and GG algorithms with a few standard multi-armed bandit algorithms like UCB, EXP3, and OSUB. However, there are many relevant algorithms in the literature, such as privacy-preserving bandits, that could provide a more comprehensive benchmarking. Including more sophisticated models that consider bidder heterogeneity and dynamic bidding strategies would offer a more rigorous evaluation.\n\nThe theoretical assumptions, particularly the unimodality of the reward function and the i.i.d. nature of bidder values, may be overly restrictive. These assumptions simplify the analysis but may not hold in real-world settings where bidder values can be correlated and vary over time. Relaxing these assumptions and exploring their impact would provide a more realistic evaluation. This could involve theoretical extensions or empirical investigations to understand the sensitivity of the algorithms.\n\nThe discussion on practical implementation lacks depth. While the paper provides theoretical guarantees and some empirical results, it does not sufficiently address the computational complexity and scalability of the algorithms. In real-world applications, especially with thousands of bidders, efficiency is crucial. A detailed analysis of computational costs and potential optimizations or approximations would benefit practitioners implementing these algorithms in large-scale systems.\n\nLastly, the paper could benefit from a detailed exploration of parameter selection and sensitivity analysis. The performance of both LG and GG algorithms depends on several parameters, such as the exploration parameter $\\alpha$ and the confidence levels $\\delta$. However, there is no thorough analysis of how to choose these parameters or their sensitivity to different settings. A comprehensive parameter study, including guidelines for selecting appropriate values, would enhance the usability of the proposed methods. This could involve both theoretical insights and empirical evaluations to provide a clear understanding of the parameter space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and questions. As you noticed, our main contributions consist in providing theoretically sound algorithms for the problem that we introduce, under some assumptions that we motivate. Our simulations allow to check\nthat our theoretical insights are valid when these assumptions are satisfied.\n\nWe believe that an extensive\nempirical evaluation would definitely be a nice addition but prefer to carry it\nin future work. Your questions about the use of synthetic data, the comparison with\nexisting methods, the unimodality and iid assumptions, the computational\ncomplexity and hyper-parameter selection are answered in the next paragraphs.\n\n(W1/Q1) As we are considering a bandit setting, we cannot use a fixed dataset\nfor experiments as the experiment needs to give the reward *depending on*\nthe action played by the algorithm. This can only be done by interacting with a\nreal-world live system or with a simulator. Even if we had the possibility to\nrun our algorithms on a live real-world system, it would make the experiment not\nreproducible. In the end, only the choice of simulator makes the experiments\nreproducible. We could have adapted to our problem the simulator available at\nhttps://github.com/amzn/auction-gym. Note however that this simulator also relies\non simple distributions for the values (ex: lognormal for the one mentioned\nabove), which is similar to what we do.\n\n(W2) We believe that our comparison with existing\nmethods is fair. It is not clear to us that the algorithms mentioned by the reviewer apply to our setting. First, while it emerges from new privacy-preserving regulations in online advertisements, our problem is different from settings where the bandit algorithm itself has to enforce some notion of privacy. Secondly, we emphasize that in our setting the individual bidders bid their values and thus there is no need to use an algorithm to specifically learn how to bid. \n\n(W3/Q3) We answer about unimodality in the general comment above. The\ncase where bidders value evolve over time would be an\ninteresting extension, that is discussed in the answer of Reviewer TZVE (Q2).\n\n(W4/Q4) In the revision, we will provide a complexity analysis in Appendix D. In both GG and LG, the most costly part in term of time-complexity is the computation of reward estimates. They are computed by replacing the integral in Equation (5) by a Riemann sum with $\\lceil{N \\sqrt{T}\\rceil - 1}$ terms (the reasoning behind the number of terms needed is the same as in the proof of Theorem 1, precisely line L664). Therefore, whenever reward estimates of a neighborhood of size $O(N)$ is needed, it cost $O(N^2 \\sqrt{T})$ operations. Note that during forced exploration steps, reward estimates are not needed and therefore the associated cost is not paid. The total time complexity therefore depends on the number of times reward estimates are needed which itself depends on the trajectory.\nHowever, our algorithms could be modified to guarantee that reward estimates are needed at most $\\log(T)$ times for instance by only performing updates at the end of a phase of exponentially increasing length. This would lead to a mean complexity per iteration of $O(N \\log(T))$.\n\n(W5/Q2) Regarding the $\\delta_t$, as standard with confidence-based algorithms we want to set it as small as possible so that the theoretical guarantees hold. This is the case if the sum in l.890 converges, which is guaranteed by the tuning that we propose in Theorem 3 (more precisely, this term becomes $\\sum_{t\\geq 1} t^{-2}$). Regarding $\\alpha$: (1) for LG we use $\\alpha=1/(\\log_{3/2}(N)+1)$, which is strongly supported by the analysis l.860-862. We will add this tuning in the statement of Theorem 2 in the revision. (2) for GG our analysis holds if $\\alpha$ is smaller than $1/2$, Theorem 3 suggests $\\alpha=\\frac1{4}$ . The tuning of $\\alpha$ does not seem crucial for its performance because it is only used after the best neighborhood is identified with large probability.\n\n(Q5) In any online setting, first-price auctions are inherently much harder to study due to the game-theoretical aspects coming from the fact that the different bidders can adapt their bidding strategy at every time step. With the symmetry assumption, a Nash equilibrium exists and is known if all bidders bid separately, but it requires the *knowledge* of the value distribution, which is exactly what the decision maker is trying to learn. Due to that, even if a stationary regime exists asymptotically, it is very hard to provide any guarantee on finite-time behavior. Generalized second-price auctions are also non-truthful and would present similar challenges, on top of requiring to extend the setting to selling multiple items at each time.\n\n(Q6) The novel concentration bounds presented in Theorem 1 are one of the major technical contributions of the paper. We provide a sketch of the proof l.161-174 of the paper and a detailed proof in Appendix B, where we first present auxiliary results before providing the complete proof. In particular, in Appendix B.1.2 we detail the concentration inequalities that we use to obtain tailored concentration bounds for each part of the integral defining the expected reward (Eq. 5). First, Theorem 1 is essential to analyze the concentration of simple estimates of $r(l)$ based on samples from an arm $n \\neq l$. Indeed, a standard Hoeffding bound can only be used to estimate $r(n)$ with rewards from arm $n$ only. Hence, none of our theoretical guarantees can be obtained without Theorem 1. Furthermore, in the proof of Theorem 1 significant effort was required to remove the $n$ factor coming from the definition of the reward (Eq. 5). As discussed in l 183-185, this result cannot be obtained with a standard Hoeffding bound.\n\n(Limitations paragraph) We will include some of the reviewers' suggestions in Appendix E.", "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": "", "extra_scores": {}}]

Author rebuttal:
**General comment**  We want to thank all the reviewers for their careful examination of our paper. We appreciate that all reviewers seem enthusiastic about the problem that we introduce, the algorithms that we propose and the theoretical contributions presented in our work.


**Unimodality of the reward function**  Following their questions, we now propose a common response for all reviewers about the unimodality assumption presented in the paper (Assumption 2). 

First, we recall (Lemma 2 in the paper) that unimodality holds for several usual families of distributions. 

Secondly, by carefully following the proofs of Theorem 2 and 3 we can remark that our theoretical results actually hold under a slightly milder assumption: it suffices that the estimation neighborhood of every sub-optimal arm contains a better rewarding arm, that is 
$n\\neq n^\\star \\Rightarrow \\exists n' \\in \\mathcal{V}(n):\\; r(n')>r(n)$   with the notation from the paper. This assumption seems easier to satisfy, especially if $p$ is large, by construction of the neighborhoods. For instance, if all arms form a single estimation neighborhood then unimodality is not needed at all.

Then, we can also consider the case where even this assumption does not hold. As pointed out by Reviewer TZVE, we provide l.311-313 of the paper a simple and sound way to adapt Greedy-Grid in that case: in Algorithm 2, (line 4 in the "for" loop) the set $\mathcal{C}_t$ 
can be redefined as follows:  $\\mathcal{C}\_t= \\{s \\in \\mathcal{S}:\\; U_s \\geq L\_\{i_t^*\} \\} $  .

Indeed, the formulation of $\\mathcal{C}\_t$ in Greedy-Grid (Algorithm 2) exploits unimodality by allowing some arms with large confidence intervals to remain eliminated if any arm on their path towards the empirical best LCB is eliminated. The consequence of that change for the theoretical guarantees is straightforward: in Theorem 3 the term $\\sum_{n \\in \\mathcal{S}} \\frac{\\log(T)}{\\Delta_n} \\wedge C_n$ (where here we use $C_n$ to denote the constant term in the theorem) becomes $\\sum_{n \\in \\mathcal{S}} \\frac{\\log(T)}{\\Delta_n}$. Furthermore, the problem-independent guarantees remain identical. Hence, **without unimodality a slight adaptation of GG achieves logaritmic regret on the subset of arms in the grid $\\mathcal{S}$, and still obtain $\\sqrt{(\\log_2(N)+|\\mathcal{B^\\star}|)T}$ problem-independent regret**. This is better than what standard UCB would obtain: logarithmic regret for **all $N$ arms**, and $\\sqrt{NT}$ for problem-independent bounds. Following the remark of Reviewer TZVE, we will formalize this discussion and the adaptation of Greedy-Grid in a dedicated appendix, that we will reference at l.313 of the paper.

Meta-review: The paper reports a study on repeated second-price auctions formulated as a structured bandit problem. The reviewers are in general positive towards the paper, acknowledging that the problem formulation, the technical results and analyses have novelties. The reviewers also pointed out a number of issues for the authors to address. I recommend acceptance to the paper, and encourage the authors to make a thorough revision of the paper addressing all the issues raised by the reviewers.
Decision: Accept (poster)