Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits

Thank you for your detailed review and questions. As you noticed, our main contributions consist in providing theoretically sound algorithms for the problem that we introduce, under some assumptions that we motivate. Our simulations allow to check that our theoretical insights are valid when these assumptions are satisfied.

We believe that an extensive empirical evaluation would definitely be a nice addition but prefer to carry it in future work. Your questions about the use of synthetic data, the comparison with existing methods, the unimodality and iid assumptions, the computational complexity and hyper-parameter selection are answered in the next paragraphs.

(W1/Q1) As we are considering a bandit setting, we cannot use a fixed dataset for experiments as the experiment needs to give the reward depending on the action played by the algorithm. This can only be done by interacting with a real-world live system or with a simulator. Even if we had the possibility to run our algorithms on a live real-world system, it would make the experiment not reproducible. In the end, only the choice of simulator makes the experiments reproducible. We could have adapted to our problem the simulator available at https://github.com/amzn/auction-gym. Note however that this simulator also relies on simple distributions for the values (ex: lognormal for the one mentioned above), which is similar to what we do.

(W2) We believe that our comparison with existing methods is fair. It is not clear to us that the algorithms mentioned by the reviewer apply to our setting. First, while it emerges from new privacy-preserving regulations in online advertisements, our problem is different from settings where the bandit algorithm itself has to enforce some notion of privacy. Secondly, we emphasize that in our setting the individual bidders bid their values and thus there is no need to use an algorithm to specifically learn how to bid.

(W3/Q3) We answer about unimodality in the general comment above. The case where bidders value evolve over time would be an interesting extension, that is discussed in the answer of Reviewer TZVE (Q2).

(W4/Q4) In the revision, we will provide a complexity analysis in Appendix D. In both GG and LG, the most costly part in term of time-complexity is the computation of reward estimates. They are computed by replacing the integral in Equation (5) by a Riemann sum with $\lceil{N \sqrt{T}\rceil - 1}$ terms (the reasoning behind the number of terms needed is the same as in the proof of Theorem 1, precisely line L664). Therefore, whenever reward estimates of a neighborhood of size $O(N)$ is needed, it cost $O(N^2 \sqrt{T})$ operations. Note that during forced exploration steps, reward estimates are not needed and therefore the associated cost is not paid. The total time complexity therefore depends on the number of times reward estimates are needed which itself depends on the trajectory. However, our algorithms could be modified to guarantee that reward estimates are needed at most $\log(T)$ times for instance by only performing updates at the end of a phase of exponentially increasing length. This would lead to a mean complexity per iteration of $O(N \log(T))$.

(W5/Q2) Regarding the $\delta_t$, as standard with confidence-based algorithms we want to set it as small as possible so that the theoretical guarantees hold. This is the case if the sum in l.890 converges, which is guaranteed by the tuning that we propose in Theorem 3 (more precisely, this term becomes $\sum_{t\geq 1} t^{-2}$). Regarding $\alpha$: (1) for LG we use $\alpha=1/(\log_{3/2}(N)+1)$, which is strongly supported by the analysis l.860-862. We will add this tuning in the statement of Theorem 2 in the revision. (2) for GG our analysis holds if $\alpha$ is smaller than $1/2$, Theorem 3 suggests $\alpha=\frac1{4}$ . The tuning of $\alpha$ does not seem crucial for its performance because it is only used after the best neighborhood is identified with large probability.

(Q5) In any online setting, first-price auctions are inherently much harder to study due to the game-theoretical aspects coming from the fact that the different bidders can adapt their bidding strategy at every time step. With the symmetry assumption, a Nash equilibrium exists and is known if all bidders bid separately, but it requires the knowledge of the value distribution, which is exactly what the decision maker is trying to learn. Due to that, even if a stationary regime exists asymptotically, it is very hard to provide any guarantee on finite-time behavior. Generalized second-price auctions are also non-truthful and would present similar challenges, on top of requiring to extend the setting to selling multiple items at each time.

(Q6) The novel concentration bounds presented in Theorem 1 are one of the major technical contributions of the paper. We provide a sketch of the proof l.161-174 of the paper and a detailed proof in Appendix B, where we first present auxiliary results before providing the complete proof. In particular, in Appendix B.1.2 we detail the concentration inequalities that we use to obtain tailored concentration bounds for each part of the integral defining the expected reward (Eq. 5). First, Theorem 1 is essential to analyze the concentration of simple estimates of $r(l)$ based on samples from an arm $n \neq l$. Indeed, a standard Hoeffding bound can only be used to estimate $r(n)$ with rewards from arm $n$ only. Hence, none of our theoretical guarantees can be obtained without Theorem 1. Furthermore, in the proof of Theorem 1 significant effort was required to remove the $n$ factor coming from the definition of the reward (Eq. 5). As discussed in l 183-185, this result cannot be obtained with a standard Hoeffding bound.

(Limitations paragraph) We will include some of the reviewers' suggestions in Appendix E.

Thank you for your careful review. First, regarding the last sentence of your summary, we want to precise that for Greedy-Grid (GG) the regret bound we obtain is the minimum between $\sqrt{(\log_2(N)+|\mathcal{B^\star}|)T}$ and a problem-dependent constant (independent of $T$). We answer your question about unimodality above, in a general comment for all reviewers. Below, we answer your second question about the comparison between the performance of Local-Greedy (LG)/OSUB and Greedy-Grid (GG).

First, we refer to the discussion at the end of the paper (l.306-337) for a detailed comparison of the theoretical results obtained with our two algorithms. We recall that both algorithms admit constant problem-dependent regret (see Theorem 2 and 3), but the scaling of the constant is better for GG, and furthermore permits to derive $O(\sqrt{T})$ problem-independent guarantees (which we cannot obtain for LG due to the local gap in the bound). Hence, from a theoretical perspective Greedy-Grid enjoys better guarantees than Local-Greedy. However, our experiments indeed show that Local-Greedy performs better in practice. In our opinion, there are several reasons that might explain this gap between theory and practice.

A first reason is that the scaling in the worst local gap in the analysis of Local Greedy (Theorem 2) might be conservative: this gap can be paid in a scenario combining bad initialization (very far from the optimal arm and with flattest part of the reward function on the path towards the optimal neighborhood) and bad luck (a ''plausibly maximal'' number of steps is taken to move in the good direction). It is likely that in practice this scenario is quite rare, and thus not seen in our experiments. Although the analysis of LG might be made slightly less conservative (see l.322-327 for a discussion), it seems impossible to completely remove some local gaps from the analysis of Local-Greedy in the worst case.

Furthermore, the analysis do not capture the fact that in some cases Local-Greedy might also be lucky and start playing in the optimal neighborhood very fast. On the other hand, this situation cannot happen for GG, which requires enough statistical evidence to eliminate all sub-optimal neighborhoods. While this step in GG is the reason for its improved theoretical guarantees, it might have an empirical cost because GG is ``always cautious'' compared to LG. Lastly, we discuss l.334-337 that another reason for that practical gap might also be that implementing LG does not require to compute confidence intervals, contrarily to GG. Hence, it is possible that the confidence intervals of Theorem 1 can be tightened, which would directly benefit to the performance of Greedy-Grid by accelerating the search for the optimal neighborhood. We leave potential refinements of the bound presented in Theorem 1 for future work. Additionally, we believe that these intuitions also hold when comparing GG and OSUB, from which LG is strongly inspired. We believe that the comparison between LG and OSUB justifies the interest of our approach from a practical perspective.

We will complete the "Experimental results" paragraph l.338 with the parts of this discussion that are not already presented in the previous paragraph l.306-337, in order to provide more intuitions about why LG works better than GG in our experiments. We believe that analyzing those two algorithms in our paper provides a good overview of what is possible to achieve: GG has the most appealing theoretical guarantees but is outperformed by LG in our experiments, suggesting LG is a better choice in practice. Whether LG can be modified to achieve the theoretical guarantees we obtain for GG is an interesting but challenging open problem.

Thank you for your detailed review and suggestions, as well as for appreciating the key contributions of our work. Regarding the unimodality assumption (W1), we answer in a general comment for all reviewers. Regarding the symmetry of bidders, see the paragraph (Q3) below.

(Q1) We apologize for the inconsistency, we will correct line 44. Indeed, our analysis is conducted by assuming that only the maximum reward is observed. However, we could use the same procedure presented in Section 2.2 if the sequence of second prices (price paid by the winner) $\\overline{S}\_{k} = (s\_{k,1}, \\dots, s\_{k, m_k})$ was observed instead of $\\overline{W}_k$. The cumulative distribution function of observations would become $G_k: x \\in [0,1] \\mapsto (k+p) F(x)^{k+p-1} - (k+p-1)F(x)^{k+p}$, and thus it is also possible to estimate any power F^\\ell from $\\overline{S}_k$ via a suitable inversion formula. Furthermore, the same could be done if both first and second prices were observed, but the inversion would be more intricate because the joint distribution of $\\overline{W}_k$ and $\\overline{S}_k$ should be considered. This might allow a slight improvement of the multiplicative constants of the result, but probably at the cost of more intricate computation. We will add this discussion at the end of Section 2.2.

(Q2) This question is indeed particularly relevant in real-world applications, thank you. First, the progressive change of distribution can imply a change in optimal arm, but also that previous observations progressively induce biased estimators. Hence, we believe that our algorithms might require some adaptation to tackle a non-stationary value distribution. Since our problem is framed as a structured MAB, it might be natural to look for inspiration in the rich literature on non-stationary MAB problems. In this literature, the general idea is to mitigate this bias by forgetting some of the past observations, either passively (with a sliding window or discount factor, see e.g. [1]) or actively (with change-point detectors, see e.g. [2]). Then, the analysis of the dynamic regret can be conducted by assuming a property of the non-stationarity, such as an upper bound on a number of changes or on the total amplitude of variations (we could imagine a budget on $\sum_{t=1}^T ||F_t-F_{t+1}||_\infty$ for instance). We believe that our algorithms can be adapted to include these ideas, and the practitioners' choice would certainly be to opt for a simple sliding window mechanism. We leave the formalization of this adaptation and its analysis for future work. We suspect that the structure of our problem might imply interesting non-trivial properties, for instance by making it easier to detect changes in the reward function because changes in $F$ can be detected when sampling any arm.

(Q3) The assumption of symmetric bidders is commonly used in the auction literature (see e.g chapter 2 of [3]) to build understanding of problems that couldn't be solved in the full generality of arbitrary bidders.

Following your comment in (W2), if we considered asymmetric bidder the action space would include all possible combinations of players from the coalition, making the problem combinatorial. In addition, the estimation of the reward function with different value distributions becomes very intricate, so overall this setting might be too difficult to actually exploit the structure of the problem.

We believe that studying the symmetric case is a necessary step to unlock addressing more complex settings in future work, such as coalitions built out of several groups of similar bidders.

[1] Garivier, Aurélien, and Eric Moulines. "On upper-confidence bound policies for non-stationary bandit problems." arXiv preprint arXiv:0805.3415 (2008).

[2] Besson, Lilian, et al. "Efficient change-point detection for tackling piecewise-stationary bandits." Journal of Machine Learning Research 23.77 (2022): 1-40.

[3] Krishna, Vijay. Auction theory. Academic press, 2009.

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.