Online Ad Procurement in Non-stationary Autobidding Worlds

Summary

This work studies an advertiser's online high-dimensional lever decision problem with long-tern constraints under limited bandit feedback for different input models. The authors' main contributions include: (1) model formulation; (2) proposing an algorithm universally applicable to input models; (3) theoretical regret analysis. There is an advertiser that repeatedly interact with an ad platform during a time horizon $T$, aiming to maximize her total conversions subject to multiple constraints. At each time $t$, the advertiser need to make a multi-dimensional lever decision and observed her realized conversion as well as her multi-dimensional realized cost. The authors propose an algorithm with universally good performance and provide regret lower bounds of this problem with respect to different input procedures.

Strengths

1. The proposed algorithm is oblivious to input models such that it can achieve high performance without knowing which setting the decision-maker is in. 2. It is novel to adopt the random perturbation approach and the expert-based decision-making in online autobidding. The regret analysis requires non-trivial insights and techniques. Particularly, the proof of lemma 4.6 that bounds the primal ascent regret stands out from standard primal-dual frameworks. 3. The organization of this paper is great.

Weaknesses

1. The idea of solving a problem in many worlds is not new. In addition to commonly studied stochastic and adversarial input models, [1] also considers $\delta$-corrupted, periodic, ergodic input models. Actually, the proofs for the latter three cases are analogous to the stochastic case as they still assume stationary distributions to some extent. [1] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. 2. Some mistakes are spotted. Some statements are not clear enough. See the questions below.

Questions

1. Line 13, multi-dimension -> multi-dimensional. 2. Line 14. What does "uncertain" mean throughout this paper? The bidder should known their constraints at the beginning, e.g. known budget. 3. Line 168, a redundant "of". 4. Line 219, realzied -> realized. 5. Line 283, violates constraints violation? 6. Line 664, missing values for $a$ and $b$. 7. Line 288, what does $\alpha$ do in algorithm 1? To my understanding, it makes sure that the opinion of an expert lies in the interior of the domain. However, the value of $\alpha$ is not specified. It seems fatal if $\alpha$ is close to 1. 8. Line 299, the number of experts $N$ seems to be negative when $T$ goes to infinity. 9. Line 301, N experts or (N+1) experts? 10. Line 539, the first term in the RHS of equation (15) is not bounded after timing $T$. 11. Line 542, $\tau$ -> $t$. The authors should check $t\in [T]$ and $\tau\in [t]$ throughout the appendix. the order of $\beta$ also seems wrong in equation (16). 12. Line 626, observe that the sum operator is over $t\in [\tau_A]$ so the optimal $x$ does not vary to $t$. Does it implies all $y_t$ are the same? 13. Line 629, arer -> are. 14. Line 636, according to the theorem 4.2 one has $\gamma_{0} = K^{-1/6} (1+DT)^{1/2} T^{-3/4}$ and $\gamma_{N} = 1$. Then $\gamma_{0}$ is not the largest element in the stepsize set since it goes to $0$. Be willing to raise my rating if it is confirmed there is no technical flaw.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This work studies the problem of dynamic online allocation under constraints with bandit feedback, and derives a generic algorithm applicable to various input settings (stochastic, adversarial, $\delta$-corrupted, ergodic, periodic). It recovers regret rates close to those of the lower bounds in each of these settings. The algorithm uses a dual gradient descent over $\lambda_t$ to decouple the decisions over time by considering the lagrangian, a gradient ascent for the optimal choice of $x_t$ (that also uses the technique from Flaxman et al (2004) to handle the bandit feedback), and finally a multiplicative weight update to adapt the learning rates used to the correct input setting.

Strengths

- The algorithm generalizes to multiple input settings and general constraints the problems related to Bandits with knapsack constraints, and of online learning with constraints. (to be clear this is an important strength of this paper!) - The problem is well motivated through the consideration of running multiple ad campaigns

Weaknesses

- The assumption that there exists some safe action of level $\beta$ do simplify the problem of constraint satisfaction by guaranteeing to be able to satisfy the constraint at the end - Some of the upper bounds (stochastic, periodic, corrupted) are a bit loose compared to their respective lower bounds - The writing can be improved, in particular in the proofs which are lacking discussion about their main ideas and intuition. As an example page $8$ of the appendices is almost only a sequence of inequality and is hard to follow. For instance the inequalities could be cut in multiple parts, and some comments could be added to better explain the goal of the proof. There are also some typos.

Questions

- Do the $T^{2/3}$ rates come from the use of the method to handle bandit feedback? How would a generic gradient feedback affect the rates, would we be able to derive tight rates with respect to the lower bounds presented? I think it might have been better to first present the results with gradient feedback, and mention in the appendix that bandit feedback can be handled by a standard technique. This would allow the main part of the paper to focus on the new contributions. - Could you give some intuition on what this optimal dynamic sequence looks like in the various settings? For instance, if my understanding is correct, the optimal dynamic sequence in the stochastic setting is simply a unique point (because the data is i.i.d). Could the optimal sequence for the ergodic setting be a function of $\kappa$ close to the unique optimal point with respect to the stationary measure? - How much does the meta algorithm degrade the regret? (compared to assuming that we know the input setting) - l 657 Why is it $... +D \dots$ and not $...+(t-1)D\dots $ ? Comments/Typos: - L304 and l324 stochstic -> stochastic - I find the notation of $\lambda \in [0,F e/ \beta]$ confusing, is it $\lambda \in [0,F/\beta]^K$? - L553 ‘which states $\max_{x \in \mathcal{X}} f(x)$: is a word missing? - L608 I am not sure to understand this statement, could you include a reference for this result? Is the sup taken over $(g_{\tau},f_{\tau})$ - over $[t]$ or $[T]$? - I think it would be nice to cite the paper of Mannor et al (Online learning with sample path constraints), which deals with very similar problem and started the works on online convex optimization with varying constraints - Equation below l643: $v$ -> $\Vert v \Vert$, and the last equality should be an inequality (as it is in the ball, not the sphere) - Equation below l655 I think some of the gradients are missing $\Vert \nabla_t \Vert^2$ and $x^i_{t+}$ -> $\tilde{x}^{i}_{t}$. Why are some of the gradients bolded and not the others? - Same thing for the gradients below l657, in addition I am not sure where $P(y_1:T)$ is defined. - L 664 ‘$a=$ and $b=$’ it is unfinished I have not read through all the proofs, but I would recommend to read it again to look for additional typos

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes the authors address some limitations in the section $5$ of the paper regarding the lower bounds.

Summary

This paper concerns a two-stage autobidding scenario, such as an advertising platform environment. Each advertiser wants to maximize value received (e.g., clicks) subject to long-run constraints (e.g., budget or ROI). As actions, the advertiser can specify certain instructions to an autobidding agent (e.g., a spend rate or ROAS target) and observe the results. The advertiser observes bandit feedback, and wishes to tune their choice of actions/instructions to solve their long-run optimization problem. Because the autobidders themselves are learning over time and potentially facing changing market conditions, the evolution of payoffs observed by the advertiser may not be stationary. The paper considers a variety of different payoff evolution models, including partial adversarial corruption, periodic, and ergodic payoffs. The main result is a universal learning method for the advertiser that achieves good regret for each of these payoff evolution models. The idea is to combine dual descent methods for constraints with a modified online convex optimization approach to adequately explore lever decisions given the dual variables. This combination leads to vanishing regret in each of the settings considered. The resulting regret rates are then compared with known lower bounds for each of these settings (many of which apply in relaxed settings, such a full feedback rather than bandit feedback).

Strengths

I like this paper. The modeling framework that separates true "long-run" objectives from "short-term" directive levers is extremely natural and, as far as I'm aware, novel. It also tracks my understanding of how autobidding works in practice: advertisers need not keep their specified constraints (to the autobidder) fixed over time, but can manipulate them online as tunable knobs. The assumption of a safe action is likewise very reasonable, and the proposed algorithm makes use of it to good effect. The proposed algorithm combines multiple well-established ideas from the online optimization literature in a reasonable way. The fact that this comes together into a unifying framework is an appealing feature, as is the need for only bandit feedback. The regret rate suffers somewhat compared to known bounds, but not by too much --- what amounts to a rate of T^{3/4} for each of the non-fully-adversarial settings is quite good, while leaving room for future work to improve. Getting these regret rates down to sqrt{T} (or showing this isn't possible) is a nice open challenge.

Weaknesses

The biggest question for me is how "real" autobidding (e.g., competitive uniform bidding) falls into this scenario. For instance: even in a stationary environment in terms of competitors, the relationship between levers and outcomes is not necessarily stationary for advertiser i because the underlying autobidder is learning over time how best to satisfy the directive communicated by a given lever setting. So my understanding is that this scenario would fall under the ergodic setting. But what if the competitors are not stationary, but are learning as well? Can these theoretical frameworks be linked back to the motivating setting of autobidders that simultaneously learn? Either way, it would be nice to have a more thorough discussion of this in the body of the paper. Another potential weakness is that the technical contributions largely synthesizes known approaches, so the marginal technical contribution is not extremely high. I therefore view the conceptual and modeling contributions as the main selling points for the submission.

Questions

Are there natural conditions under which a scenario with mutually competing autobidders would fall into one of the analyzed worlds?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

I feel that the paper is sufficiently up-front about its limitations, and the authors do an adequate job of describing what their paper does and does not do.

Summary

The paper proposes a universally constrained online learning framework for ad procurement in non-stationary autobidding worlds. The paper makes contributions to the field by addressing the challenges of ad procurement in non-stationary autobidding worlds and developing a unified algorithm that can perform well in autobidding world while satisfying long-term constraints.

Strengths

- The paper addresses the challenges of ad procurement in non-stationary autobidding worlds and develops a unified algorithm that can perform well in autobidding world while satisfying long-term constraints. - The paper makes contributions to the field by developing an algorithm that yields good performance guarantees under different procedures. - The paper is well-written and clearly presents the problem and the proposed solution.

Weaknesses

- The paper does not have experiments to validate the theoretical findings. - The paper could provide more insights into the practical implications of the proposed algorithm and how it can be applied in real-world settings.

Questions

What are the challenges with applying the algorithm to obtain experimental results?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.