Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits

Authors: dorian  baudry
hugo  richard
maria  cherifa
clément  calauzènes
vianney  perchet
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 11:44:24

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.

Main paper: 
 introduction: 
 The online display advertising has seen remarkable evolution in recent decades [14, 30, 33, 25] . Publishers, who are the suppliers of digital ad space on 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 advertising, 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 as a 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 of impressions won minus their costs. This raises a fundamental question: how many ad campaigns should participate in the auction to optimize the overall utility? In 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 a small number of campaigns can make it difficult to secure impressions, while securing the spot with a large number of bidders inevitably raises the price due 38th Conference on Neural Information Processing Systems (NeurIPS 2024).to competition. In this paper, this problem is formalized and solved via novel Multi-Armed-Bandit (MAB) algorithms.Problem statement Consider a sequence of T ad impressions sold through second price auctions (see [20] for a survey). At auction t ∈ [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 a price equal to the second highest bid. The decision maker (the DSP) runs N ∈ N * advertising campaigns forming a coalition. At time t, two groups of bidders participate: (1) n t ∈ [N ] bidders from the coalition chosen by the decision maker ex-ante -without knowing the realization of the bidders' values -and (2) p ∈ N * other bidders, that we call the competition. When a 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 1. 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, 22] , known as 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 a weakly dominant strategy in this case. Lastly, assuming a known number of competitors p is frequently seen in auction models (see for instance [20] chapter 3.2.2). Under Assumption 1, the expected reward received by the decision maker at time t is given by r(n t ), where r is the expected reward function, defined byEQUATIONwhere v (1) and v (2) are respectively the first and second maximum of v, and [n] is used to abbreviate {1, . . . , n}. The problem therefore reduces to a MAB where the decision maker chooses arms n 1 , . . . , n T ∈ [N ] sequentially and aims to minimize its cumulative expected regret R(T ) defined by R(T ) = t≤T r(n * ) -r(n t ) , with n * = argmaxEQUATIONgiven that privacy constraints from the browser [8] 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 be formulated as a Multi-Arm Bandits (MAB, see [21] for a survey). In MAB, a learner repeatedly selects from a 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 ([2, 7, 17] , to name a few), the most popular approaches arguably remain exponential weights algorithms (EXP3, [4] ) 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 being linear bandits [1] , Lipschitz bandits [23] , or unimodal bandits [9, 28, 29] . The problem considered here is novel in the literature of structured bandits, arising from the observability restrictions coming with privacy-enhancing systems. Still, in the next section we show that unimodality -in this 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, [9] ).Last, the use of online learning algorithms to tackle repeated auction problems have been explored in various contexts ( [26, 12, 5, 32, 27, 11] ). However, none of these works approach the problem through the perspective of a coalition of bidders, and are thus not applicable to this setting. EXP3 [4] O( √ N T ) UCB1[3] O n∈[N ] log(T ) ∆n ∧ √ N T OSUB [9] O log(T ) ∆ n ⋆ +1 + log(T ) ∆ n ⋆ -1 + n∈[N ]The proof of Lemma 2 can be found in Appendix A.2. Note that the Complementary Beta distributions [19] , chosen for technical reasons, are similar to Beta distributions and any Beta distribution can be approached by a Complementary Beta. Furthermore, in Appendix A. 3 we present experiments suggesting that r is unimodal for all p ∈ N * if F is the c.d.f of 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, so Assumption 2 is reasonable in practice. We furthermore discuss in Section 3.2 the adaptation of our algorithms if this was not the case. 
estimation of powers of f: 
 Consider the feedback W k = (w k,1 , . . . , w k,m k ) gathered after playing arm k and winning the auction m k times. W k , 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 [10] ). The distribution of any element of W k has cumulative distribution function F k : x ∈ [0, 1] → F k+p (x), which clearly exhibits a one-to-one mapping between F k (x) and F (x). Hence, given W k , for any ℓ ∈ N we can estimate F ℓ byF ℓ k+p : x → ( F k+p (x)) ℓ k+p, whereEQUATION)Estimation of r Consider any arm n ∈ [N ]. Following Equation ( 3), it appears that estimating both F n+p and F n+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 k ∈ [N ], by using the simple estimateEQUATIONFurthermore, 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 to different feedback). A similar procedure can be derived for a setting where the sequence of second prices would be observed instead. Indeed, their distribution would beG k : x ∈ [0, 1] → (k + p)F (x) k+p-1 -(k + p -1)F (x)k+p , which can lead to a reward estimate 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.We now introduce the first theoretical contribution of this paper: confidence bounds on the deviations of an empirical estimate r k (n) w.r.t. the true expected reward r(n).Importance of (relatively) local estimation In principle, (5) suggests that samples from any arm k ∈ [N ] can provide a simple estimate of the reward function of any other arm n ∈ [N ]. However, we establish that the position of k w.r.t. n significantly impacts the concentration of r k (n). Intuitively, the ratio(n + p)/(k + p) determines how the uncertainty on F k+p propagates on the reward after performing the inversion to obtain an estimate of F n+p . Indeed, considering any i ∈ N, if for some x ∈ [0, 1] the deviation F (x) i -F i (x) is small then a first order approximation provides thatEQUATIONHence, a small error on F (x) i is multiplied by j i F i (x) j i -1 to obtain the resulting error on F (x) j . For j ≥ i this term can be as large as j/i while for j < i it can be arbitrarily large if F i (x) is very small. This observation motivates a restriction on the range of arms that can be used to estimate the reward of a given arm n, that we call its estimation neighborhood. We use the convention that arms smaller than 1 or greater than N exist but have not collected any sample and have a known reward of 0.Definition 1 (Estimation neighborhood of an arm n). Assume3 that p ≥ 4 Then, the estimation neighborhood of n is the rangeV(n) = [v ℓ (n), v r (n)] = k ∈ [N ] : k + p ∈ n+p 2 , 3 2 (n + p -1). We call v ℓ (n) and v r (n) respectively the furthest left and right neighbor of n.Theorem 1 (Concentration of simple estimates). Consider any n ∈ [N ] and k ∈ V(n). Let r k (n) be defined according to (5) from m k samples collected by k. Then, there exists some constants β k,n (depending on n, k, p) and ξ k,n,F (additionally depending on F ) such that, with probability 1 -δ,EQUATION)Furthermore, the constants admit universal upper bounds for any n, k, p, F . For instance if m k ≥ 4 it holds that β k,n ≤ 33 and γ k,n,F ≤ 100.Proof sketch (see Appendix B for the detailed proof). The first ingredient consists in approximating the reward formulation (3) by a Riemann sum: for some step sizeD -1 > 0, it holds that r k (n) - r(n) = n D D-1 s=0 E(x s ) + err D , with x s = s/D for all s ∈ {0, . . . , D -1}.In Lemma 4 we use elementary properties of F to show that the approximation error satisfies err D ∈ [0, nD -1 ]. Next, we upper and lower bound E(x s ) with different concentration bounds according to the value of F k,s := F (x s ) k+p . More precisely, for any δ ∈ (0, 1) the following bounds hold each with probability at least 1 -δ,           | F k (x s ) -F k,s | ≤ F k,s × 3 log( 2 δ ) m k if F k,s ∈ I 0 := 3 log(2/δ) m k , 1 (Chernoff) , F k (x s ) ≤ 6 log(2/δ) m k if F k,s ∈ I 1 := δ m k , 3 log(2/δ) m k (Chernoff) , F k (x s ) = 0 if F k,s ∈ I 2 := 0, δ m k (union bound) .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 s ∈ {0, . . . , D -1}. The interval I 0 provides the first term in (7) , which is dominant in terms of m k , and we make β k,n fully independent of F by carefully using some properties of the reward function. The two remaining intervals I 1 and I 2 provide the second term in (7) , and γ k,n,F depend on F through the boundaries of the interval I 1 . The corresponding factor in ξ k,n,F can be bounded by 1 or estimated in practice (see Appendix B.4).In Appendix B, we give the expression of β k,n and ξ k,n,F and provide in (17) and (19) fully explicit upper and lower confidence bounds on r k (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 β k,n and ξ k,n,F do not diverge for any value of the problem parameters. We now provide more high-level comments on the derivation of this result.The proof of Theorem 1 is non-trivial, and the careful usage of the Chernoff bounds that we introduced is crucial to obtain tight bounds on r k (n) for two reasons. First, it seems necessary to concentrate estimates from arms k > 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 β k,n 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 n seems difficult in general, so our proof provides a way to mitigate its cost by multiplying it by a higher power of m -1 k , at least m-2 3 k (if k + p = 3 2 (n + p -1)). This is the theoretical motivation for the definition of V(n) (Definition 1): while k + p = 2(n + p -1) would lead to theoretically valid results, it would not ensure that the linear term in n is second-order in m k .We now conclude this section by exhibiting a condition on F that allows to reduce the scaling of the confidence bound in n to logarithmic terms. Lemma 3 (Improved bound for Lipschitz quantile function). Assume that k ∈ V(n) and F -1 is L-Lipschitz, then there exists an absolute constant ξ such that with probability 1 -δ it holds that| r k (n) -r(n)| ≤ β k,n log 2⌈n √ m k ⌉ δ m k + ξL log 4⌈n √ m k ⌉ δ   log 2⌈n √ m k ⌉ δ m k   n+p-1 k+p (8)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 to 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 1.Both rely on the use of simple estimates of r(n) (see Section 2) by arms present in its estimation neighborhood V(n) (see Definition 1) and theoretically motivated by Theorem 1. In this section, for ease of exposition, we describe algorithms as if feedback was collected at every time steps. In Appendix C.1, we show that the algorithms and their guarantees only require a slight adaptation when the feedback is collected only when the auction is won. 
local-greedy: 
 We first present Local-Greedy (LG), which is a natural adaptation of a standard policy in unimodal bandits, OSUB [9] .The main idea of OSUB is to 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 to efficiently exploit the structure of the problem considered: at each round t, LG defines a reference arm ℓ t , called leader, but plays greedily in the neighborhood V(ℓ t ), based on simple power estimates computed with samples from ℓ t only. In addition a sampling requirement, implemented by a parameter α ∈ (0, 1), is used in order to ensure the good concentration of these estimates. We detail Local-Greedy in Algorithm 1 below.EQUATION)) ; ▷ Compute estimates from the leader If m t := |{s ∈ [t -1], n s = ℓ t }| ≤ αt: play n t = ℓ t ;▷ Linear sampling requirement Else:play n t ∈ argmax n∈V(ℓt) r ℓt (n) ; ▷ Greedy play in V(ℓt) Observe w ∼ F nt+p ; ▷ Record feedbackHigh-level properties of LG First, using Greedy instead of UCB is only possible because of the structure of the problem: when ℓ t is well-explored the estimates of arms in V(ℓ t ) computed with samples from ℓ t 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 ℓ t is well explored.A second property is that since |V(ℓ t )| grows with ℓ t , a sequence of locally optimal moves (best play in a given neighborhood) allows to reach the optimal arm exponentially fast (in O(log(N )) steps), which is particularly interesting in practice if N is large. On the other hand, LG might suffer from the inherent drawback of any "local" policy: identifying a high-rewarding arm in a 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 an initial exploration phase. We propose Greedy-Grid, 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 implementation (and performance) of the algorithm.The concept of Greedy-Grid is very intuitive: it plays a Local-Greedy 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 a Successive-Elimination procedure [13] on a subset of arms forming a 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 1), and can hence mutually estimate themselves and all arms in between (Theorem 1). 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 a sufficiently long time.Following Definition 1, we construct S := {s i } i≥1 recursively: s 1 = 1, and for i ≥ 2 we set s i+1 = max {s ≥ s i : s ∈ [N ], s ∈ V(s i ), s i ∈ V(s)}.v S l (n) = 0 if n < min S, v S r (n) = N + 1 if n > max S and (v S l (n), v S r (n)) = argmin (x,y)∈S\{n}: n∈[x,y] (y -x) otherwise . We call the "bin" of arm n all arms between its left and right neighbors:B(n) = {n ∈ [N ], v S l (n ′ ) < n < v S r (n ′ )}.For simplicity we use the notationB ⋆ = B(n ⋆ ) 4 .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 a specific bin (and, as we will see, play greedy). This choice depends on an elimination procedure: an arm k 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 * t of the arm with the best LCB, then the unimodality assumption implies that k should also be eliminated. The set of arms not eliminated at t is called C t in Algorithm 2.To compute the UCB (U n ) and LCB (L n ) of an arm n, we elect a leader ℓ n which is the arm in [v S l (n), v S r (n)] that was played the most in the last t rounds and then compute the bounds based on ℓ n , using Theorem 1. We show in the proof of Theorem 3 that this procedure ensures that a linear number of samples in t is used to compute the UCB and LCB of arms in B ⋆ with high probability.If at least one arm is not eliminated (C t is not empty), arms in C t are played one after the other (Round Robin). If all arms in the grid are eliminated, GG plays greedily in the bin B(i * t ) of the arm with the highest LCB. The empirical reward of each arm n ∈ B(i * t ) is computed similarly as U n and L n using samples from the leader ℓ n . GG then plays the best empirical arm αt times which is the same sampling requirement as LG.The careful design of Greedy-Grid 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 a sub-optimal part of the reward function. However this guarantee comes at a cost: if n ⋆ 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.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: O and O n For any x > 0, we use the notation O(x) to describe a quantity that scales in x, up to logarithmic terms in x and N (hence the notation is linked to the problem). Furthermore, Algorithm 2 Greedy Grid Input: Grid S, confidence levels (δ t ) t∈N , sampling parameter α Play n 1 = min S and observe w ∼ F n1+p for t ≥ 2 do ∀n ∈ [N ] ℓ n = argmax k∈[v S l (n),v S r (n)] m k |{u ∈ [t -1], n u = k}| ; ▷ Elect leaders ∀n ∈ [N ], L n = L ℓn (n,(C n ) n∈[N ]\{n ⋆ } , each satisfying C n = O N ∆n ∆ 2 , such that R T ≤ n∈[N ]\n ⋆ C n .Additionally, if the arm set forms a single estimation neighborhood, that is ∀n ∈[N ] : V(n) ⊃ [N ], then each constant C n can be refined to O n ∆ -1 n , providing R T = O( √ N T), 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 a full information scenario. This explains why GG achieves both constant regret depending on the gaps, and a gap-independent bound in √ N T . Furthermore, the hidden logarithmic constants come from carefully using Theorem 1 to separate the linear term in n 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 t necessarily implies a locally sub-optimal play, in some estimation neighborhood, at some point in the past (maximized by the chosen value of α). 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 gap ∆ 2 .Theorem 3 (Regret upper bound for Greedy-Grid). Suppose that GG is tuned with confidence level δ t = 1 N 2 t 3 , and α = 1/4. Then, for any T ∈ N it holds thatR T = O N n∈B ⋆ 1 ∆ n + n∈S log(T ) ∆ n ∧ ∆ n 1{n < n ⋆ } ∆ 2 v l (n ⋆ ) + 1{n > n ⋆ } ∆ 2 vr(n ⋆ ).Additionally, it holds that R T = O (K + |B ⋆ |)T , for K = ⌊log 3/2 (N )⌋.Proof sketch (see Appendix C.4 for the detailed proof). First we prove that, w.h.p., during a linear time range in t GG either played the grid or in B ⋆ . Hence, arms n ∈ [N ]\{S ∪ B ⋆ } are played a (universal!) constant number of times by GG in expectation. Then, for n ∈ S the term in log(T ) ∆n comes from the standard analysis of UCB [3] ; while the constant bound comes from exploiting that after 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 ∈ B ⋆ is derived similarly as the first bound of Theorem 2.Discussion First, we show that being able to estimate r(n) from the feedback obtained after playing an arm k 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 ∆, while for the latter only the actual gaps ∆ n (with n ⋆ ) are involved. This difference permits to obtain a problem-independent guarantee for GG for any configuration of p and N . Furthermore, its scalingK + |B * | ≤ 2n * + ⌊log 3/2 (N )⌋ can be much smaller than √ N if n * is small.Then, we would like to discuss the impact of the concentration bound presented in Theorem 1 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 definition of r(n). A feature of our concentration bound is that the linear scaling in n does not appear in the first order term. Informally, this allows to exhibit terms of orderO N (∆ -1 n ) in the regret analysis instead of O(N 2 ∆ -1n ), which can be significantly better for small gaps. A remark here is that the size of the grid in GG could be optimized as a larger grid makes the second order term in Theorem 1 smaller but is paid linearly in the regret.We nevertheless highlight some potential for improvement in the analysis of LG. First, the local gaps ∆ in the bound of LG could be replaced by (in spirit, referring to S for simplicity)min n∈[N ] |r(v S l (n)) - r(v S r (n))|.It is clear though that this gap remains "local" and can be arbitrarily smaller than ∆ n for some arms n ∈ [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 β k,n and ξ k,n,F 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 a focus on a 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.LG relies heavily on Assumption 2, GG can be readily adapted to handle non-unimodal reward functions. This is done by modifying the definition of the set of non-eliminated grid arms C t to {s ∈ S, U s ≥ L i * t } in Algorithm 2. In that case, the algorithm can no longer eliminate arms on 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 O(log(T )) term persists for n ∈ S in Theorem 3, while the problem-independent bound remains unchanged. Although we believe unimodality is 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|-armed bandit, rather than an N -armed bandits with |S| = O(log(N )) ≪ N for large N .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 to the other approaches. Although GG offers more robust theoretical guarantees, particularly with sub-linear problem-independent bounds, LG proves to be more effective 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 in practice and was not encountered in our experiments. Additionally, Local Greedy benefits from scenarios where it starts playing in the optimal neighborhood only after a few steps, a situation GG cannot exploit due to its need for sufficient statistical evidence to 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 to the tightness of the confidence intervals in Theorem 2, a 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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. • The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a 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 or 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). 
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 n n+p an observation of a sample of the distribution with c.d.f F n+p .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 T thanks to new concentration bounds introduced in Theorem 1. 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 to 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, a DSP can launch campaigns through multiple auctions, an interesting question is whether the current analysis could be extended to the case of A auctions where a play at time t is (n a,t ) a∈ [A] where a∈[A] n a,t = N and the reward is a∈[A] r a (n a,t ) with r a determined by integers p a , n a,t and F a in the same way that r depends on p, n t and F . How to explore each auction in parallel in an efficient manner and how to handle the case where some auctions must be assigned zero players are then the main questions to solve. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to usage guidelines or 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 a best faith effort.12. Licenses for existing assets Question: 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? Guidelines:• The answer NA means that the paper does not 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 not available online, the authors are encouraged to reach out to the asset's creators.  
 
 Appendix: 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 1 Lemma 1. The expected reward function defined in Equation (1) satisfies,EQUATIONProof. Given v = (v i ) i∈[n+p] ∼ F × • • • × F , we have r(n) = E (v (1) -v (2) )1 argmax i∈[n+p] v i ∈ [n] (i) = E (v (1) -v (2) ) E 1 argmax i∈[n+p] v i ∈ [n] (ii) = E v (1) -E v (2) × n n + p = n n + p × 1 0 P(v (1) > x) -P(v (2) > x)dx = n n + p × 1 0 P(v (2) ≤ x) -P(v (1) ≤ x)dx (iii) = n n + p × 1 0 ((n + p)F n+p-1 (x) -(n + p -1)F n+p (x) -F n+p (x))dx = n 1 0 (F n+p-1 (x) -F n+p (x))dx .The first equality is the definition of r(n) in Equation (1) . Equality (i) follows by independence of the index of the maximum and the value of the maximum and second maximum. This is itself a 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 a consequence of the fact that the values are i.i.d. Lastly, equality (iii) follows from [10] (Equation 2.1.3) where for k ∈ {1, 2}, it is shown thatP(v (k) ≤ x) = n+p i=n+p-k+1 n + p i (1 -F (x)) n+p-i F (x) i ,and the proof is concluded by substitution.As a preliminary, we formally define the non-usual distributions considered in Lemma 2.Truncated exponential distribution Let a > 0 be some parameter. Then, we define a truncated exponential distribution of parameter a as the distribution with c.d.f. F : x → 1-e -ax 1-e -a . Hence, F (0) = 0 and F (1) = 1, and the density of this distribution is the same as the density of the exponential distribution with same parameter on the segment [0, 1], up to a normalization constant.Complementary Beta distribution Lemma 2. Let F be the cumulative distribution function of a Bernoulli, truncated exponential or Complementary Beta distribution. Then, for any p ∈ N * , r in Equation (3) unimodal.Proof. We consider each family of distributions separately.Bernoulli distributions If F is the c.d.f. of B(q) (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 1, and every other player draw a value of 0. Hence, we obtain that r(n) = nq(1 -q) n+p-1 , which is trivially unimodal and maximized in n ⋆ = -1 log(1-q) ∨ 1, regardless of the size of the competition.Truncated exponential distributions Let a > 0 be the parameter of the distribution. Let Q(x)be the inverse function of F (the quantile function), defined byQ(x) = 1 a log 1 1-x(1-e -a ) = 1 a +∞ k=1 x k (1-e -a ) k k .Let's denote by q(x) the derivative of Q(x), denoted by q(x) = +∞ k=0 λ k x k where λ k = 1 a (1-e -a ) k . Introducing theses functions allows us to rewrite r(n) as follows,r(n) = n 1 0 F (v) p+n-1 (1 -F (v))dv = n 1 0 x p+n-1 (1 -x)q(x)dx using F (v) = x = n 1 0 x p+n-1 (1 -x) +∞ k=0 λ k x k dx = +∞ k=0 λ k n p + n + k - n p + n + k + 1 = n n + p λ 0 + n +∞ j=1 1 n + p + j (λ j -λ j-1 ) = λ 0 (1 - p n + p ) + +∞ j=1 (1 - p + j n + p + j )(λ j -λ j-1 ) = λ 0 - p n + p + +∞ j=1 λ j-1 -λ j λ 0 θj p + j n + p + jwhere the last inequality follows since lim j→∞ λ j = 0. Remark that θ j ≥ 0 since λ j is decreasing and∞ j=1 θ j = 1. The derivative of r(n) is given by, r ′ (n) = λ 0 p (n + p) 2 - +∞ j=1 θ j p + j (n + p + j) 2 = λ 0 Θ p (n) - ∞ j=1 θ j Θ p+j (n) = λ 0 Θ p (n) 1 - ∞ j=1 θ j Γ p,p+j (n) where Γ p,p+j (n) = Θ p+j (n) Θ p (n)the functions Γ p,p+j (n) are non-decreasing hence it is the same for their convex combination. As sign(r′ (n)) = sign(1 - ∞ j=1 θ j Γ p,p+j (n)) it follows that sign(r ′ (n)) is decreasing meaning r(n) is unimodal.Complementary beta distributions Using the same change of variable as in the previous proof (Y = F (X)), we express the reward as follows,r(n) = n × E Y ∼Q Y n+p-1 (1 -Y ) ,where Q denotes the quantile function associated with c.d.f F (i.e. F -1 ). By definition of F , Y follows a Beta distribution of parameters (a, b). We can thus compute the expected reward by using the explicit formula for moments of the Beta distribution,E X∼B(a,b) [X n+p-1 -X n+p ] = n+p-2 k=0 a + k a + b + k - n+p-1 k=0 a + k a + b + k = n+p-2 k=0 a + k a + b + k × 1 - a + n + p -1 a + b + n + p -1 = n+p-2 k=0 a + k a + b + k × b a + b + n + p -1 .Thanks to this expression, we prove the unimodality by analyzing the ratio r(n+1) r(n) , that we first write asr(n + 1) r(n) = n + 1 n × a + n + p -1 a + b + n + p -1 × a + b + n + p -1 a + b + n + p = n + 1 n × a + n + p -1 a + b + n + p ,and then obtain that this ratio is larger than 1 if and only if(n + 1)(a + n + p -1) ≥ n(a + b + n + p) ⇐⇒ n(a + n + p) + a + p -1 ≥ n(a + n + p) + bn ⇐⇒ n ≥ a + p -1 b ,which concludes the proof by showing the unimodality and expressing the value of the critical point.The proof of Lemma 2 highlights that the unimodality assumption is satisfied as soon as the quantile function, expressed as a power series, has its coefficients that slowly decrease (indeed, the k-th coefficient just needs to be smaller than 1 -1 k times the k -1-th one). Similarly, the second proof technique highlights (up to standard algebraic manipulations) that unimodularity is guaranteed as soon as the function n→ 1 -E[X n+p-1 ]/E[X n+p-2 ] is log- concave.In this section, we plot the shape of r(n) for some additional families of distribution that we conjecture to be unimodal from the plots.The following figure, illustrate the unimodal shape of r(n) for different parameters for the Beta distribution and p. We now provide and discuss an example where Assumption 2 is not satisfied.Let us consider a discrete distribution supported on {0, 0.5, 1}. The counter-example emerges from putting all the probability mass in 0.5: let us consider a small ϵ > 0, identify F with {ϵ, 1 -ϵ, 1} and assume that there is no competition (p = 0). Then, we can verify with (3) thatr(n) = n 2 (ϵ n-1 + (1 -ϵ) n-1 -(ϵ n + (1 -ϵ) n )) = n 2 (ϵ n-1 (1 -ϵ) + ϵ(1 -ϵ) n-1 )Consider ϵ = 0.15, we get up to a precision 0.001 the values: (r(n)) Before presenting the proof of the theorem, we present two auxiliary results that are essential to its development.The first result consists in upper bounding the deviation of a Riemann sum approximation of r(n) (for some n ∈ [N ]) with respect to its exact integral formulation. This result is also of practical interest, since it can prevent computing exact integrals at 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 n ∈ [N ], D ∈ N, and define the grid(x s ) s∈{0,...,D-1} = 0, 1 D , . . . , D-1 D. Then, the expected reward approximationr(n) = n × 1 D D-1 s=0 F (x s ) n+p-1 -F (x s ) n+p satisfies |r(n) -r(n)| ≤ n D .Proof. For any j ∈ N we considerS j = 1 D D-1 s=0 F j (x s ) as an approximation of I j = 1 0 F j (x)dx .We recall that since F j is a c.d.f., it is monotone, increasing and satisfies F j (0) = 0 and F j (1) = 1. This means that for any s ∈ {0, . . . , D -1}, it holds that ∀x ∈ [x s , x s+1 ], F j (x s ) ≤ F j (x) ≤ F j (x s+1 ). The linearity of the integral first provides thatI j = 1 0 F j (x)dx = D-1 s=0 s+1 D s D F j (x)dxThen, using this decomposition and the monotony of F j we obtain thatS j ≤ 1 D D-1 s=0 F j s D ≤ 1 0 F j (x)dx ≤ 1 D D-1 s=0 F j s + 1 D ≤ 1 D D-1 s=0 F j s D + 1 D D-1 k=0 F j s + 1 D -F j s D ≤ 1 D D-1 s=0 F j s D + F j (1) -F j (0) D = S j + 1 D .Therefore, we obtained that for any j ∈ N it holds that S j ≤ I j ≤ S j + 1 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 -1 and j = n + p.In the following lemma, we summarize the different concentration bounds that we use in the proof of Theorem 1.Lemma 5 (Mutltiplicative Chernoff bounds). Let µ m be the empirical average of m i.i.d. Bernoulli random variables X 1 , . . . , X m with expectation µ. Then, for any δ > 0, each of the following bounds holds with probability at least 1 -δ,       | µ m -µ| ≤ √ µ × 3 log( 2 δ ) m if µ ∈ I 0 := 3 log(2/δ) m , 1 , µ m ≤ 6 log(2/δ) m if µ ∈ I 1 := δ m , 3 log(2/δ) m , µ m = 0 if µ ∈ I 2 := 0, δ m .Proof. We first tackle the case µ ∈ I 2 , where the bound is obtained by remarking that P(µ m > 0) ≤ P(∃i ∈ [m] :X i = 1) ≤ mµ ≤ δ.The two other cases are obtained by using the multiplicative form of the well-known Chernoff bounds [16] , that provide that∀γ > 0, P( µ m ≥ (1 + γ)µ) ≤ e -m γ 2 µ 2+γ, and∀γ ∈ [0, 1], P( µ m ≤ (1 -γ)µ) ≤ e -m γ 2 µ 2 .When considering γ ≤ 1 we can further write thatP(| µ m -µ| ≥ γµ) ≤ 2e -m γ 2 µ 3 .On the other hand, for γ ≥ 1 the bound for the lower deviation is trivially 0 while the bound for the upper deviation can be written as follows,γ ≥ 1 ⇒ P( µ m ≥ (1 + γ)µ) ≤ e -m γ 2 µ 2+γ ≤ e -m γ 2 µ 3γ = e -mµ γ 3 .Hence, the case separation between the intervals I 0 and I 1 simply consist in identifying the value µ for which a probability 1 -δ can be obtained by setting an appropriate γ ∈ [0, 1] or for γ > 1 in the above inequalities. More precisely, inverting the first bound provides γ = µ-1 2 3 log( 2 δ ) m , which is valid only if µ -1 2 3 log( 2 δ ) m ≤ 1 ⇒ µ ≥ 3 log( 2 δ ) m. This leads to the first confidence interval when µ ∈ I 0 . The same procedure for µ ∈ I 1 leads to γ = µ -1 3 log( 2 δ )m, which provides the result stated in the lemma. This concludes the proof.Theorem 1 (Concentration of simple estimates). Consider any n ∈ [N ] and k ∈ V(n). Let r k (n) be defined according to (5) from m k samples collected by k. Then, there exists some constants β k,n (depending on n, k, p) and ξ k,n,F (additionally depending on F ) such that, with probability 1 -δ,EQUATION)Furthermore, the constants admit universal upper bounds for any n, k, p, F . For instance if m k ≥ 4 it holds that β k,n ≤ 33 and γ k,n,F ≤ 100.Proof. We build the proof from the Riemann sum approximation of the reward presented in Lemma 4 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 r k (n) byr k (n) = 1 D D-1 s=0 F k+p,m k s D n+p-1 k+p -F k+p,m k s D n+p k+p.Thanks to Lemma 4, we know thatr k (n) ∈ r k (n) -n D , r k (n) + n D .For the rest of proof, we introduce the notationF j s = F s D j for any j ∈ [N ], F k+p s = F k+p,m k s D , and F s,k,n = F k+p,m k s D n+p k+p , so that r k (n) := 1 D D-1 s=0 F s,k,n-1 -F s,k,n ,that we want to relate withr(n) := 1 D D-1 s=0 F n+p-1 s -F n+p s .We use that each variable F s,k,n can be expressed as the expectation ofm k i.i.d. Bernoulli random variables of expectation F k+p s , since F k+p,m k = 1 m k m k j=1 1{X k,j ≤ x}.Hence, we can use the confidence intervals providing by Lemma 5, according to the value of F k+p s . We define two critical values, corresponding to the switch between the different intervals I 0 , I 1 , I 2 in the lemma, and their closest upper point in the discretization grid. The first isx 0,k = F -1 δ m k 1 k+p, and s 0,k = ⌈Dx 0,k ⌉ , and we recall that below x 0,k it holds that F k,i,n-1 = 0 with probability larger than 1 -δ. Then, we definex 1,k := F -1   1 ∧ 4 log 2 δ m k 1 k+p   , and s 1,k := ⌈Dx 1,k ⌉ .We remark that we use a multiplicative factor 4 inside of F -1 , while Lemma 5 might suggest to use 3. We do that for technical reasons, that we will motivate at one stage of the proof. These terms depend both on the sample size m k and the confidence level δ, but we omit them in the notation for simplicity. Then, for fixed values of these constants we decompose the estimator between the intervals I 0 = {s 1,k , . . . , D -1}, I 1 = {s 0,k , . . . , s 1,k -1}, and I 2 = {0, . . . , s 0,k -1}. Note that for the second interval to be non-empty it must hold that s 0,k ≤ s 1,k -1, that we assume in the following, otherwise we can just remove this interval from the analysis. For s ≥ s 1,k , Lemma 5 guarantees that with probability larger than 1 -δ it holds thatF k+p s ∈ (1 -γ s )F k+p s , (1 + γ s )F k+p s for γ s = F -k+p 2 s 3 log 2 δ m k ,while for k ≤ s 1,k -1 we can use one of the two other bounds provided in the lemma. Using a union bound, all the confidence intervals hold simultaneously for the points in the sum and in x 1,k with probability larger than 1 -(D + 1)δ, which defines a "good" eventEQUATIONFor the rest of the analysis, we assume that G holds. In particular, in that context there existsD -s 1,k constants (z s ) s∈{s 1,k ,...,D-1} such that ∀s ∈ I 0 , F k+p s = (1 + z s )F k+p s and z s ∈ [-γ s , γ s ].We now upper and lower bound r k (n) using these constants, first writing that under G it holds thatr k (n) = 1 D D-1 s=0 F s,k,n-1 -F s,k,n = 1 D D-1 s=s 1,k F s,k,n-1 -F s,k,n + 1 D s 1,k -1 s=0 F s,k,n-1 -F s,k,n = 1 D D-1 s=s 1,k (1 + z s ) n+p-1 k+p F n+p-1 s -(1 + z s ) n+p k+p F n+p s + 1 D s 1,k -1 s=s 0,k F s,k,n-1 -F s,k,n ,where we used that all the terms are zero for indices smaller than s 0,k . We can thus express r k (n) as follows,r k (n) = r(n) + nE 0 + nE 1 , with E 0 := 1 D D-1 s=s 1,k ((1 + z s ) n+p-1 k+p -1)F n+p-1 s - 1 D D-1 s=s 1,k ((1 + z s ) n+p k+p -1)F n+p s, andE 1 := 1 D s 1,k -1 s=s 0,k F s,k,n-1 -F s,k,n - s 1,k -1 s=0 F n+p-1 s -F n+p s ,so we can upper and lower bound r i (n) by upper and lower bounding E 0 and E 1 separately.Bounding the individual terms of E 0 For any k ≥ s 1,k we consider the termE 0,s := ((1 + z s ) n+p-1 k+p -1)F n+p-1 s -((1 + z s ) n+p k+p -1)F n+p s .We first re-arrange it in a more convenient way, remarking thatF n+p-1 s = F n+p-1 s (F s + (1 -F s )) = F n+p s + F n+p-1 s (1 -F s ).Using this result, we obtain thatE 0,s := ((1 + z s ) n+p-1 k+p -1)F n+p-1 s -((1 + z s ) n+p k+p -1)F n+p s = ((1 + z s ) n+p-1 k+p -1)F n+p-1 s (F s + (1 -F s )) -((1 + z s ) n+p k+p -1)F n+p s = F n+p s ((1 + z s ) n+p-1 k+p -1) -(1 + z s ) n+p k+p + 1) + F n+p-1 s (1 -F s )((1 + z s ) n+p-1 k+p -1) ,which simplifies toEQUATIONWe remark that these two terms have opposite sign, E + 0,s having the same sign as z s . We first upper bound E 0,s , starting with the case z s > 0, for which it holds thatz s ≥ 0 ⇒ E 0,s ≤ E + 0,s ≤ ((1 + γ s ) n+p-1 k+p -1) cs F n+p-1 s (1 -F s ) .The constant c k is explicit from the definition of γ s , and the bound holds for any i ∈ [N + p] without restriction. However, if we only consider the case n+p-1 k+p ≤ 2 then we can further write thatc s ≤ (1 + γ s ) 2 -1 ≤ 2γ s + γ 2 s ≤ 3γ s , since γ s ≤ 1for the values of s considered. Then, for z s ≤ 0 we use thatz s ≤ 0 ⇒ E 0,s ≤ E - 0,s ≤ F n+p s ((1 + z s ) n+p-1 k+p -(1 + z s ) n+p k+p ) = F n+p s (1 + z s ) n+p-1 k+p 1 -(1 + z s ) 1 k+p .Using the notation y s = -z s for convenience, we upper bound the last multiplicative term as follows,(1 -y s )1 k+p = e log(1-ys) k+p ≥ 1 + log(1 -y s ) k + p = 1 - 1 k + p log 1 + y s 1 -y s ≥ 1 - 1 k + p × y s 1 -y s ,which leads toy s := -z s ≥ 0 ⇒ E 0,s ≤ E - 0,s ≤ F n+p s (1 -y s ) n+p-1 k+p y s (k + p)(1 -y s ) = F n+p s (1 -y s ) n+p-1 k+p -1 y s k + p .We now remark that when k + p ≤ n + p -1 then the bound simply becomes E - 0,s ≤ F n+p s × γs k+p . However, when k+p > n+p-1 the upper bound is diverging when y s gets close to 1. Since the upper bound is increasing in γ s , and using that nEQUATION. This is the motivation for calibrating the thresholds 1,k so that k ≥ s 1,k ⇒ (1 -γ s ) 1 3 ≥ 1 2, which is done by tuning s 1,k so that γ s 1,k ≤ 7 8 (hence the multiplicative 4 inside of F -1 ). We thus obtain thatz s ≤ 0, k ≥ s 1,k ⇒ E 0,s ≤ 2F n+p s γ s k + p ,which finally leads toEQUATION)We now proceed to lower bound E 0,s , using again Equation (10) . The proof is similar to the proof of the upper bound, for the case z s ≥ 0 we can write thatz s ≥ 0 ⇒ -E 0,s ≤ -E - 0,s ≤ F n+p s (1 + z s ) n+p-1 k+p ((1 + z s ) 1 k+p -1) ≤ F n+p (1 + γ s ) n+p-1 k+p γ s k + p ≤ 2 n+p-1 k+p F n+p γ s k + p ,using the concavity of x → (1 + x)1k+p and that γ s ≤ 1. Then, for the case z s ≤ 0 we use thatz s ≤ 0 ⇒ -E 0,s ≤ -E + 0,s ≤ F n+p-1 s (1 -F s ) 1 -(1 + z s ) n+p-1 k+p ≤ F n+p-1 s (1 -F s ) 1 -(1 -γ s ) n+p-1 k+p . If n+p-1 k+p ≤ 2 we furthermore obtain that (1 -γ s ) n+p-1 k+p ≥ (1 -γ s ) 2 ≥ 1 -2γ s , so z s ≤ 0 ⇒ -E + 0,s ≤ 2γ s F n+p-1 s (1 -F s ) .Combining these results, we can lower bound E 0,s as follows,EQUATIONwhere the terms involved in this lower bound are analogous to the terms used in the upper bound up to some multiplicative constants.Summary: bounds on E 0 We start with the lower bound. Using Equation (12) , we obtain thatnE 0 ≥ - n D D-1 s=s 1,k 2 n+p-1 k+p γ s k + p F n+p s ∨ 2γ s F n+p-1 s (1 -F s ) ≥ - 3 log 2 δ m k ×    n D D-1 s=s 1,k 2 n+p-1 k+p F n+p-k+p 2 s k + p + n D D-1 s=s 1,k 2F n+p-1-k+p 2 s (1 -F s )   The first sum can be trivially upper bounded by 2 n+p-1 k+p n k+p , which cannot be refined without more restrictive assumptions on F . For the second term, we use that k + p ≤ 3 2 (n + p) to exhibit the reward function associated with a number of players n ′ := n -n(k+p) 2(n+p) ≥ n 4 and a competition of size p ′ := p -p(k+p) 2(n+p) ≥ p 4 .n D D-1 s=s 1,k F n+p-1-k+p 2 s (1 -F s ) = n × 1 D D-1 s=s 1,k F n ′ +p ′ -1 s (1 -F s ) ≤ n × 1 0 F (x) n+p-1 4 (1 -F (x))dx + n D = n n ′ × n ′ 1 0 F (x) n ′ +p ′ -1 (1 -F (x))dx + n D ≤ n n ′ + p ′ -1 + n D = n n + p -k+p 2 + n D ,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 thatEQUATIONwhere the worst scaling for the left-hand term in the maximum is attained in k + p = 3 n+p 2 and provide 2 n n+p , while for the right-hand term it is achieved in k + p = n+p-1 2 and provides 2 n n+p-1 . As we already discussed, the upper bound can be expressed very similarly, remarking that the bound involving the terms γ s /i have to be divided by two, and the other term have to be multiplied by 3/2. We hence directly obtain thatEQUATION)Bounds on E 1 We start by upper bounding the second sum by 0. Under G we hence obtain thatnE 1 ≤ n D k∈I1 ( F k+p s ) n+p-1 k+p ≤ n D k∈I1 8 log(2/δ) m k n+p-1 k+p ≤ n x 1,k -x 0,k + 1 D 8 log(2/δ) m k n+p-1 k+p, which has a worst possible power of 2/3 when m k ≥ 8 log(2/δ), corresponding to k + p = 3 2 (n + p -1). Replacing x 1,k by its expression, we further obtain thatEQUATION)For the lower bound on nE 1 1 , we apply the exact same steps, remarking that the constant 8 at the very first step can be replaced by 4, since we now use the exact value of F k+p in the upper bound. Furthermore, we have to remove the term x 0,k . We finally obtainEQUATION)Summary: bounds on r k (n) We conclude this proof by summarizing the results, and exhibiting the constants introduced in the theorem. First, by combining ( 13) and ( 16) we obtain the following lower bound,r k (n) ≥ r(n) - n D -n 4 log(2/δ) m k n+p-1 k+p ×    F -1   1 ∧ 4 log 2 δ m k 1 k+p   + 1 D    -4 n 2(n + p) -(k + p) + n 2D + 2 n+p-1 k+p -2 × n k + p × 3 log 2 δ m k .Then, by combining ( 14) and ( 15) we obtain the following upper bound,r k (n) ≤ r(n) + n D + 6 n 2(n + p) -(k + p) + n 2D + n 3(k + p) × 3 log 2 δ m k + n 8 log(2/δ) m k n+p-1 k+p ×    F -1   1 ∧ 4 log 2 δ m k 1 k+p   -F -1 δ m k 1 k+p + 1 D    .As a final step, we recall that in this proof 1 -δ is the confidence level of the point estimate in each of the D points (x s ) s∈{0,...,D-1} and x 1,k . Hence, to obtain a confidence 1 -δ on the full estimate r k (n) we need to multiply δ by (D + 1) in the bounds presented above. As a final step, we choose D + 1 = ⌈n √ m⌉, so that the term n D ≤ 1 √ m k becomes a second order term in the bounds. After replacing δ and D by the appropriate values, we hence obtain thatEQUATIONwithEQUATIONEQUATIONSymmetrically, we obtain thatEQUATIONwithβ + k,n = 6 √ 3 n 2(n + p) -(k + p) + n 2(⌈n √ m k ⌉ -1) + n 3(k + p), andEQUATIONHence, we obtain the statement of ( 7) by choosingβ k,n = β - k,n ∨ β - k,n and ξ k,n,F = ξ + k,n,F ∨ ξ - k,n,F. Furthermore, it is clear from their expression and the constraint k + p ∈ n+p 2 , 3 n+p 2 that these two constants are bounded by by absolute constants. Their expression provided in the theorem comes from choosing the worst admissible value of k for each of their components. This concludes the proof of the theorem.Remark 2 (Improved constants for practical implementations). We can further improve the constants of the bounds according to the position of i with respect to n + p -1.• In Equation (11) (upper bound): the constant 3 can be improved to 1 if i ≥ n + p -1, while the constant 2 can be improved to n+p-1 k+p if i ≤ n + p -1.• In Equation (12) (lower bound): the constant 2 on the right-hand side can be improved to1 if n + p -1 ≤ i.These improved constants translate easily to the upper and lower bounds presented in (13) and (14).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 k ∈ V(n) and F -1 is L-Lipschitz, then there exists an absolute constant ξ such that with probability 1 -δ it holds thatEQUATIONProof. As the result indicates, the improvement comes from providing finer upper and lower bound on the term nE 1 in the proof of Theorem 1. We can start the refined analysis from Equations ( 16) and (15) .Let us consider first the upper bound. In that case, the main ingredient comes from refining the upper bound of the difference x 1,k -x 0,k . To do that, we first provide an upper bound on 1 ∧4 log( 2 δ ) m k 1 k+p -δ m k 1 k+p. We recall that, as in the previous proof, this δ should be multiplied by ⌈n √ m k ⌉ at the end of 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 to1 - δ m k 1 k+p = 1 -e -1 k+p log( m k δ ) ≤ 1 k + p log m k δ ≤ 1 k + p log 4 log(2/δ) δ = 1 k + p × log 4 δ + log log 2 δ .For the alternative case we obtain a similar result,4 log 2 δ m k 1 k+p - δ m k 1 k+p = 4 log 2 δ m k 1 k+p 1 - δ 4 log(2/δ) 1 k+p ≤ 4 log 2 δ m k 1 k+p × 1 k + p × log 4 δ + log log 2 δ ,so the two upper bounds simplify to   1 ∨ 4 log 2 δ m k 1 k+p    × 1 k + p × log 4 δ + log log 2 δNext, we use the assumption that F -1 is L-Lipschitz to obtain thatn(x 1,k -x 0,k ) := n   F -1   1 ∧ 4 log 2 δ m k 1 k+p   -F -1 δ m k 1 k+p   ≤ Ln k + p × log 4 δ + log log 2 δ ≤ 4 Ln n + p × log 4 δ .By substituting δ by δ/(⌈n √ m k ⌉) we obtain that the linear dependency in n obtained with the previous analysis is refined to a log4⌈n √ m k ⌉ δfor the upper bound, which matches the result at this point.We now consider the lower bound, and work on refining the upper bound of the term -nE 1 in the proof of Theorem 1. To do that, we consider a new intermediary pointx ′ 0,k = F -1 δ m×n k+p n+p-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-nE 1 ≤ n D k∈I1 F n+p-1 s nE 0 1 + n D k∈I2 F n+p-1 s nE 1 1.We remark that we can use the upper bound provided for n(x 1,k -x 0,k ) to upper bound nE 1 1 , obtaining the same result up to some multiplicative constants. Hence, it remains to upper bound E 0 1 , for which additional steps are needed. However, we will simply use the exact same trick as before: we consider another sub-interval I ′ 2 , for which this time it holds thatk ∈ I ′ 2 ⇒ F k+p s ≤ δ m×n k+p n+p-1. Then, we have thatnE 0 1 = n D k∈I ′ 2 F n+p-1 s + n D k∈I2\I ′ 2 F n+p-1 s ≤ n D k∈I ′ 2 1 n δ m k n+p-1 k+p + n D k∈I2\I ′ 2 δ m k n+p-1 k+p ≤ |I ′ 2 | D δ m k n+p-1 k+p + n × |I 2 | -|I ′ 2 | D δ m k n+p-1 k+p.Just as before, we show that|I0|-|I ′ 0 | D cannot be too large if the quantile function is Lipschitz. More precisely, we obtain that δ m k 1 k+p - δ m k n k+p n+p-1 1 k+p = δ m k 1 k+p log(n) n + p -1, so that we can finally write that nE 0 1 ≤ δ m k n+p-1 k+p + n × δ m k 1 k+p × log(n) n + p -1 × L + 1 D × δ m k n+p-1 k+p ≤ δ m k n+p-1 k+p + n × log(n) n + p -1 × L + 1 n √ m k × δ m k n+p-1 k+pThe UCB and LCB in Equation ( 17) and Equation ( 19) depend explicitly on the unknown F via ξ + k,n,F and ξ - k,n,F and therefore cannot be used in the implementation of GG.Below, we give empirical UCB ( U k (n, δ)) and LCB ( L k (n, δ)) by replacing ξ + k,n,F and ξ - k,n,F by empirical estimates ξ + k,n and ξ - k,n :EQUATION)where β - k,n and β + k,n are defined in Equation ( 18) and Equation ( 20), andξ - k,n = 4 n+p-1 k+p dk+p + 1 ⌈n √ m k ⌉ -1 , ξ + k,n = 8 n+p-1 k+p dk+p + 1 ⌈n √ m k ⌉ -1 for dk+p = inf{d ∈ {0, . . . , ⌈n √ m k ⌉ -1}, F k+p d ≥ 8 log(2⌈n √ m k ⌉/δ) m k }if the infimum exists and dk+p = 1 otherwise.It is a corollary of Theorem 1 that U k (n) and L k (n) are indeed high probability upper and lower bounds of the true reward: Corollary 1 (Explicit upper and lower bounds). It holds thatP( L k (n, δ) ≤ r(n) ≤ U k (n, δ)) ≥ 1 -δ Proof. With D = ⌈n √ m k ⌉ and x 1,k = F -1 1 ∧ 4 log 2⌈n √ m k ⌉ δ m k 1 k+pthe good event G defined in Equation ( 9)implies that with probability 1 -δ the following event H holds:H =    ∀k ≤ ⌈Dx 1,k ⌉, F k+p s ≤ 8 log 2⌈n √ m k ⌉ δ m k    .Under H, and since by definitionF k+p dk+p ≥ 8 log(2⌈n √ m k ⌉/δ) m k , it holds that dk+p D ≥ x 1,k = F -1   1 ∧   4 log 2⌈n √ m k ⌉ δ m k   1 k+p    This implies that ξ - k,n ≥ ξ - k,n,F and ξ + k,n ≥ ξ + k,n,F. Therefore, we can incorporate in the proof of Theorem 1 the fact that the good event G implies ξ - k,n ≥ ξ - k,n,F and ξ + k,n ≥ ξ + k,n,F and obtain the stated result.In this section, we consider the case where a feedback (in the form of a sample from a power of F ) is gathered only when an auction is won. If this is not the case, the decision-maker only knows that the coalition lost the auction. Therefore, if at time t, n t agents are assigned to an auction and the auction is lost, it makes sense to continue assigning n t agents to the auction at time t + 1, in order to gather the information that the algorithm wanted to obtain. The meta algorithm called CoMAB for coalition multi-armed bandits described in Algorithm 3 implements this strategy.Init: J 0 = ∅, m = 1 Input: Algo for t = 1 . . . T do if t >F nt+p Set J m = J m-1 ∪ {(w nt , n t , m)} ; ▷ Record feedback obtained when winning Update m = m + 1Local-Greedy and Greedy-Grid are then defined as CoMAB applied on π LG and π GG for local greedy and greedy-grid respectively. These policies associate a play n m to an history J m-1 . In Algorithm 1 and Algorithm 2, the policies are 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 is observed after each request.Lemma 6 (Regret of CoMAB). Consider a policy π that associate to every J m-1 a play n π m . Define J 0 = ∅ and J m = J m-1 ∪ {w n π m , n π m , m} where w π nm is a sample from a distribution with c.d.f F n π m +p and n π m = π(J m-1 ). Consider m π n (m) the number of times π returns n after m calls of π. After T iterations, CoMAB based on π has regret:R T ≤ N n=1 E[m π n (T )] p + n n (r(n * ) -r(n))Proof. Call n t the play chosen by CoMAB at time t, η t = 1{The auction is won at time t} ,m n (t) = |{ρ ≤ t, n ρ = n and η ρ = 1}|the number of times that n is played and the auction is won up to time t andZ n,m (t) = |{ρ ≤ t, n ρ = n and m ≤ m n (ρ) < m + 1}|the number of times that n has been played between the m-th time n won an auction and the m + 1-th time. Note that m n (t) ≤ m π n (t) since at time t, π has been called at most t times.The regret of CoMAB satisfies:R T = T t=1 E[r(n * ) -r(n t )] = N n=1 E T t=1 1{n t = n} (r(n * ) -r(n)) = N n=1 E   mn(T ) m=1 Z n,m (T )   (r(n * ) -r(n)) = N n=1 E   mn(T ) m=1 Z n,m (T )   (r(n * ) -r(n)) ≤ N n=1 E[m π n (T )] p + n n (r(n * ) -r(n))where in the second to last inequality, we used the independence between n t = n and Z n,mt(n) (T ) as n t = n depends only on the history at times t < m t (n) while Z n,mt(n) (T ) depends only on times t ≥ m t (n).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 7 (Lemma 4 from [6] ). For any ζ ≥ 1, the mappingf ζ : x ∈ [(ζ + 2) ζ ∨ 3, ∞) → sup t ∈ N : t log(t) ζ ≤ x satisfies f ζ (x) ≤ (ζ + 2) ζ × log(x) ζ x.Proof. We start by remarking that the function g(x) = x log(x) ζ is strictly increasing for all x ≥ e ζ . Now, consider a value s = Ax log(x) ζ for some A > 0, such that s ≥ 3 ∨ e ζ . By the monotonicity of t (log t) ζ , we have thatt > s ⇒ t (log(t) ζ > s (log(s) ζ = x × A log(x) ζ (log(A) + log(x) + ζ log(log(x))) ζ .Then, for x ≥ A ≥ 3, it holds that log(A) + log(x) + ζ log(log(x)) ≤ (ζ + 2) log(x), so we can simply choose A = (ζ + 2) ζ to obtain the result.All that is left is to verify that for this choice, s = (ζ + 2) ζ × log(x) ζ x ≥ 3 ∨ e ζ , but(C n ) n∈[N ]\{n ⋆ } , each satisfying C n = O N ∆n ∆ 2 , such that R T ≤ n∈[N ]\n ⋆ C n .Additionally, if the arm set forms a single estimation neighborhood, that is ∀n ∈[N ] : V(n) ⊃ [N ], then each constant C n can be refined to O n ∆ -1 n , providing R T = O( √ N T), which holds even when the reward function is not unimodal.Proof. First, we denote by r t (n) the reward estimate used for arm n at time t, and by r k,t (n) its value when the arm used to compute the estimate is fixed to k ∈ V(n). The proofs rely on concentration bounds on r t (n) derived from Theorem 1, with a confidence level δ t 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 a random variable, as well as its sample size m k (t). This issue is tackled with appropriate union bounds. Furthermore, in order to simplify the presentation we denote by E(m, δ) the maximal diameter (as a function of k) of the confidence interval provided by Equation ( 7), defined by a number of plays m of the arm used to estimate, and by a confidence level δ. More precisely, with notation of Theorem 1, for any(k, n) ∈ [N ] 2 we write that | r k,t (n) -r(n)| ≤ E(m k (t), δ t) with probability at least 1 -δ t . Furthermore, E(m k (t), δ t ) is increasing in δ t and decreasing in m k (t). Finally, we use the notation K = ⌈log 3/2 (N )⌉, so that α = 1 K+1 . 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 n is pulled at time t, then it is either pulled "on purpose" or due to forced sampling. However, it it forced sampled then it 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 eventG t = {∀s ∈ {t -⌊αt⌋, . . . , t}, (∀k ∈ V(n) : m k (s) ≥ αt), | r k,s (n) -r(n)| ≤ E(m k (s), δ s )} .Using Theorem 1, G t holds with probability at least 1 -|V(n)|t 2 δ t , where we used a crude union bound on the values of s, k and m k (t) (t could be replaced by t -⌊α⌋t⌋). Using this result, we first upper bound the number of plays of n up to horizon T as follows,E T t=1 1{n t = n} ≤ E T t=1 1{∃s ∈ {t -⌊αt⌋, . . . , t} : r s (n) ≥ r s (n ⋆ )} ≤ E T t=1 1{∃s ∈ {t -⌊αt⌋, . . . , t} : r s (n) ≥ r s (n ⋆ )} 1{G t } + T t=1 P( Ḡt ) .As discussed above, the second term satisfiesT t=1 P( Ḡt ) ≤ +∞ t=1 |V(n)|tδ t .In order to make it constant, we choose δ t = 1 |V(n)|t 4 . For the first term, we use that ∀s ∈ [αt, t], E(m k (s), δ t ) ≤ E(α(1 -α)t, δ t ) and that n can be played only if the two confidence intervals overlap. Hence, we further obtain thatE T t=1 1{n t = n} ≤ E T t=1 1{2E(α(1 -α)t, δ t ) ≥ ∆ n } + +∞ t=1 |V(n)|t 2 δ t-⌊αt⌋ = E T t=1 1{2E(α(1 -α)t, δ t ) ≥ ∆ n } + +∞ t=1 (1 -α) -4 t -2 = t α,n + π 2 6(1 -α) 4 , = t α,n + π 2 6 1 + 1 K 4 , since α = 1 K + 1 ,and for a deterministic constant t α,n defined byt α,n = sup{t ∈ N : 2E(α(1 -α)t, δ t ) ≥ ∆ n } .We recall that K = ⌈log 3/2 (N )⌉ is used to simplify the notation. The last step consists in upper bounding the value of t α,n explicitly according to n and ∆ n . Considering some t ≥ 4 ∨ n + 1, from Theorem 1 we know that there exist universal constants β and ξ, and we obtain thatEQUATION.Since α = 1 K+1 it holds that α(1 -α) = 1 K+1 K K+1 ≥ 1 2(K+1) .We then get that for some universal constants β ′ and ξ ′ , it first holds that:EQUATIONwhere we bounded log(t)t 2 3by log(t) t . Without this simplification, we also obtain thatEQUATIONThe different scaling proposed in the theorem then come from using Lemma 7 on ( 23) and (24) , taking the minimum between the two (since both bounds are valid simultaneously), and for the latter splitting cases depending on t log(t) ≤ n 6 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 andx = 4 ∆ 2 n × β ′ √ K + 1 + n(K + 1) 2 3 ξ ′ 2 ,which leads to t α,n ≤ 3x log(x). This provides the term O n 2 ∆ 2 n of the result, and constants in the logarithmic terms can be recovered explicitly by recovering the values of β ′ and ξ ′ .We then obtain the left-hand term of the result by considering (24) . Lemma 7 first provides thatn log(t) t 1 6 ≤ 1 for t ≥ 18n 6 log(n) (first bound).Still using Lemma 7, this simplification permits to use ζ = 1 and the thresholdy = 4 ∆ 2 n × β ′ √ K + 1 + (K + 1) 2 3 ξ ′ 2 ,and an upper bound of t α,n ≤ 3y log(y), but only if this term is larger than 18n 6 log(n). This provides the remaining terms of the bound, and again the logarithms can be easily recovered by computing β ′ and ξ ′ .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-Greedy are (1) that the arm n t played in t is the best empirical arm in the neighborhood of V(n t-1 ), according to the simple estimates computed with samples from n t-1 , and (2) that n t = n t-1 if m nt-1 (t) < αt (forced sampling). Hence, similarly to the previous proof we use that n t 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 t being pulled because of a greedy play in the recent rounds. More precisely, we use thatEQUATION)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 a reference arm ℓ, playing n ∈ V(ℓ) is locally optimal if n = argmax k∈V(ℓ) r(k). In that case, n is the best neighbor of ℓ, and we use thenotation n = v + (n).Furthermore, a sequence of successive locally optimal plays is an optimal path towards n ⋆ . By construction of V, an optimal path contains at most K := O(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 ⋆ is at the other. By design of V (Definition 1) we obtain that n ⋆ is reached in ⌈log 3/2 (N )⌉ 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 played only if it is located on an optimal path from another sub-optimal arm to n ⋆ . We formalize it with the following result.Lemma 8 (Existence of a "recent" sub-optimal play). For any time step t ∈ [T ] and arm n ̸ = n ⋆ , it holds that{n t = n} ⊂ A t := ∃s ∈ (1 -α) K t, t , l ∈ [N ], l ′ ∈ V(l) : r s (l) ≤ r s (l ′ ), m s (l) ≥ α(1 -α) K t and r(l) > r(l ′ ) ,Proof. Starting from (25) , we first use that either n ̸ = v + (ℓ s ), and in that case playing n is locally sub-optimal so this event belongs to A t , or n = v + (ℓ s ). Let us now consider this second case: by definition of the leader, ℓ s was played right before the sequence of forced plays of n started, which must have happened at least as recently as t -⌊αt⌋ -1. From that point, the recursion pattern is clear: ℓ s must have been selected in the last ⌊α(s -1)⌋, by either being a locally sub-optimal play or not. The first case is included in A t , why the second requires to add another step in the analysis. Furthermore, the arm used to estimate ℓ s 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 -α) of the number in the previous step, we finally obtain that there have been a sub-optimal greedy play in the last (1 -α) K t, t steps.Before going further, we justify the tuning α = 1 K+1 , by stating that it maximizes α(1 -α) K (used later in the proof). At this step, we can simplify the notation by remarking that(1 -α) K = K K + 1 K ≥ e -1 ,hence we replace (1 -α) K by e -1 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 ⋆ is 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,H t = ∀s ∈ e -1 t, t , ∀n ∈ [N ], ∀k ∈ V(n) : m k (s) ≥ e -1 1 + K t, | r k,s (n) -r(n)| ≤ E(m k (s), δ s )} .Then, for any t K ∈ N we can upper bound the number of plays of each sub-optimal arm n ∈ [N ] as follows,E T t=1 1{n t = n} ≤ E   t≥1 1{A t }   ≤ t K + E   t≥t K 1{A t , H t }   + t≥t K P( Ht ) ,with the slight abuse of notation that E is now defined with the 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 a single neighborhood. We first choose δ t = 1 N 2 t 4 , and obtain that t≥t K P( Ht )≤ +∞ t=1 1 e -4 t 2 ≤ π 2 6e -4 .Next, we tune t K large enough so that E t≥t K 1{A t , H t } = 0. This can be done by choosingt K = sup t ∈ N : 2E e -1 1 + K t, δ t ) ≤ ∆ .where ∆ = min n∈[N -1] {|r(n + 1) -r(n)|}.We then deduce the result by applying the exact same steps as for the upper bound of t α,n , by carefully replacingδ t = 1 |V(n)|t 4 by δ t = 1 N 2 t 4, and α(1 -α)t by e -1 1+K t. Lemma 7 then allows to easily obtain the desired scaling, and to make the upper bound explicit by substitution. Since K is logarithmic in N , it is clear that it only contributes to the bound only by logarithmic factors.Theorem 3 (Regret upper bound for Greedy-Grid). Suppose that GG is tuned with confidence level δ t = 1 N 2 t 3 , and α = 1/4. Then, for any T ∈ N it holds thatR T = O N n∈B ⋆ 1 ∆ n + n∈S log(T ) ∆ n ∧ ∆ n 1{n < n ⋆ } ∆ 2 v l (n ⋆ ) + 1{n > n ⋆ } ∆ 2 vr(n ⋆ ).Additionally, it holds that R T = O (K + |B ⋆ |)T , for K = ⌊log 3/2 (N )⌋.Proof. As the theorem suggests, we will use different arguments depending on the position of n with respect to the grid and the optimal bin B ⋆ . Before that, we introduce the crucial result of this proof: for each time t large enough, thanks to the design of Greedy-Grid, all arms in optimal bin B ⋆ are estimated with a simple estimate computed with a linear number of samples in t.Following the implementation of GG, at each time t and for each arm n ∈ [N ], a confidence interval[LCB t (n), UCB t (n)] is computed so that r(n) ∈ [LCB t (n), UCB t (n)] with probability at least 1 -δ t .Similarly to the proof of Theorem 2, we consider a "good event" stating that all confidence intervals where valid on a given time range before t,G t = ∀s ∈ 3t 16 , t , ∀n ∈ [N ], r t (n) ∈ [LCB t (n), UCB t (n)] .It is clear that+∞ t=1 P( Ḡt ) ≤ +∞ t=1 N 2 tδ ⌈ 3t 16 ⌉, 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 G t , there is at least one arm in the bin B ⋆ that was played a linear number of times in t.Lemma 9 (Linear number of plays in B ⋆ under G t ). Under G t , there exists an arm n ∈ B ⋆ ∪ {v S ℓ (n ⋆ ), v S r (n ⋆ )} satisfying m n (3t/4) ≥ t 4K ∧ t 8 , where we call K = |S| = ⌊log 3/2 (N )⌋.Proof. G t guarantees that any play during the interval t 4 , t (including those due to forced sampling), were decided with valid confidence intervals. Indeed, starting at 3t 16 we are sure that all forced exploration launched before that time is completed in t/4. Furthermore, it is also direct from the design of the algorithms that, if r s (n) ∈ [LCB s (n), UCB s (n)] and Greedy-Grid is not forced to sample the previous arm it must hold that (1) it is playing the grid, or (2) it is playing an arm in B ⋆ . Indeed, no arm from a sub-optimal bin would eliminate its best neighbor.We consider two cases. First, if an arm n ∈ B ⋆ was played between rounds t 4 and t 2 . In that case it has collected at least t 8 samples before t, thanks to forced sampling. In the alternative case, the grid was played between those these two rounds, which incurs t 4K plays of argmax s∈S r(s) since by G, argmax s∈S r(s) is not eliminated when the grid is played. Then, notice that argmax s∈S r(s) ⊂ {n * , v S ℓ (n ⋆ ), v S r (n ⋆ )}. The result follows by combining the two cases.Without loss of generality, we assume in the following that K ≥ 2 (if this is not the case, just replace K by max(K, 2)). As a direct consequence of Lemma 9, using Theorem 1,under G t there exists some constant β and ξ (coming from the bounds of the theorem multiplied by 2 √ 4 = 4) such that the LCB of arm n ⋆ satisfiesEQUATION)To simplify the notation, we 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 T t=1 1{n t = n, G t } 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 to forced sampling to actual decisions by stating that, if n t = n, then there exists a round s between t -⌊t/4⌋ and t such that GG requested a pull of arm n from a "grid play" or a "greedy play".Case 1: n ∈ S. In that case if n is pulled then, since there is no forced sampling for the arms of the grid it directly holds thatEQUATION)On the other hand, under G t it holds thatUCB t (n) ≤ r(n) +      β K log 2⌈N √ t⌉ δt m n (t) + N × ξ   K log 2⌈N √ t⌉ δt m n (t)   2 3      E ′ (t) , so pulling arm n is possible only if E(t) + E ′ (t, m n (t)) ≥ ∆ n , that we simplify to 2E ′ (t, m n (t)) ≥ ∆ n or 2E(t) ≥ ∆ n .Considering the second term leads to a constant problem-dependent bound, analogous to t α,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 m n (t) is large or not. This explains why we obtain a UCB-like ( O(log(T ))) upper bound with this technique. We use thatt ≤ T ⇒ log t 2⌈N √ t⌉ δ t ≤ log T 2⌈N √ T ⌉ δ T = O(log(T )) .Then, similarly to proof of Theorem 2, we mitigate the asymptotic scaling in N by noticing that if m n (t) = Ω(N 6 ) then N mn(t)1 6simplifies. In that case, we obtain a sub-Gaussian confidence interval, and similarly to the analysis of UCB [3] we obtain that arm n is only pulled at most O log(T ) ∆ 2 n ∨ N 6 times with high probability. This is the first part of the result for n ∈ S.Proof. The proof follows the exact same steps as the proof of Theorem 3 presented in Appendix C.4. To adapt the arguments to GG-NU, we first remark that it suffices to identify which part of the proof uses the definition of the set C t . We then find that this is the case when analyzing the Case 1 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: a 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 t . We easily verify that the steps for the logarithmic bound remain valid with the new definition of C t , while the second bound clearly does not hold. This completes the adaptation of Theorem 3 (for GG) into Theorem 4 (for GG-NU).All the code for the experiments is written in Python. We use Matplotlib for plotting [18] , Numpy [15] for numerical computing and Scipy [31] for scientific and technical computing. Scipy 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 a 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 t, the algorithm decide a number of bidders n t to send to the auction and the values of all bidders (coalition and competition) v ∈ {0, 1} nt+p are sampled according to B(0.05). With probability nt nt+p , the reward v (1) -v (2) is received and v (1) 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 is reported as the expected regret R(t) in Figure 3 . Error bars represent the first and the last decile.In this simulation, the parameters are chosen to allow for having a significant number of players while keeping a gap ∆ large enough (about 2 × 10 -4 ) 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 is expected. However GG has a much higher regret than LG and only outperform UCB and EXP3 for horizons greater than 10 5 , when it starts to eliminate 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 to 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 a couple hundreds or thousands time steps while the other algorithms are still in the transient linear regime. 2 .The time-complexity of both GG and LG mainly comes from the computation of reward estimates. They are computed by replacing the integral in Equation ( 5) by a Riemann sum with ⌊N √ T ⌋ terms (the reasoning behind the number of terms needed is the same as in the proof of Theorem 1. Therefore, whenever reward estimates of a neighborhood of size O(N ) is needed, it costs O(N 2 √ 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 are needed at most O(log(T )), times for instance by only performing updates at the end of phases of exponentially increasing length. This would lead to a mean complexity per iteration of O(N 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 to the O(N ) cost of the baselines (which is even O(1) for OSUB).The collection of user data should be carried out with the preservation of user privacy in mind. This issue is at the forefront of recent, ongoing developments, such as the European Union'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 to user data. This paper tackles one such challenge by detailing Multi-Armed Bandit (MAB) algorithms that Demand Side Platforms (DSPs) can use to determine the number of ad campaigns that should partake in the repeated auction for ad placements, without the need for prior knowledge of each campaign's value. This study is therefore a 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. 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 are encouraged to create a 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, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.This assumption simplifies the presentation but our theoretical results can easily be adapted for p <if n -1 and n + 1 are included by default in V(n).We assume a unique optimal arm for simplicity, but the analysis holds if several successive arms are optimal.This concludes the proof for the problem-dependent in the favorable case where all arms are neighbors, remarking that these upper bounds just have to be multiplied by ∆ n and summed over n ∈ [N ] to convert into the regret bound. Furthermore, the problem-independent guarantee can be derived from taking the minimum between the bound and ∆ n T , remarking that the worst case is ∆ n = T -1/2 if we omit the logarithms. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: (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.

(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?
questions: 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?

(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)?

(Q3) What if bidders are asymmetric?  See (W2).
limitations: limitations: **Suggestions:**

(1) Capitalize "Coalition Gain" in title.

(2) Line 2: "their values"
paper_summary: paper_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).
strength_weakness: strength_weakness: 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". 

Also, 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.
questions: questions: 1. Can the authors provide intuitions on what will happen to the proposed algorithms when the function $r(n)$ is not unimodal? 
2. 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: limitations: The authors have addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Another 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.

The 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.

The 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.

Lastly, 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.
questions: 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?
2. 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.
3. 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?
4. 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?
5. 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?
6. 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: 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.

Comments: title: Keep rating 6
comment: Thank you to the authors for their detailed rebuttal, which has addressed most of my concerns. I will maintain my positive rating.
Thanks for your kind response! I'm keeping my score positive.
I read the authors' response.  All of my concerns except for W1 (unimodal $r$) are resolved.  For W1, the authors' response on how to relax the unimodal assumption looks promising.  Nevertheless, I understand that the authors cannot provide the full formal argument during rebuttal, which makes it difficult to verify the correctness of this argument -- the devil is always in the details.  With that said, I am still positive with this paper because I think other strengths outweigh this minor weakness, so I keep recommending weak accept.