Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2201.07139 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909942074572800 |
|---|---|
| author | Castiglioni, Matteo Nuara, Alessandro Romano, Giulia Spadaro, Giorgio Trovò, Francesco Gatti, Nicola |
| author_facet | Castiglioni, Matteo Nuara, Alessandro Romano, Giulia Spadaro, Giorgio Trovò, Francesco Gatti, Nicola |
| contents | In online marketing, the advertisers aim to balance achieving high volumes and high profitability. The companies' business units address this tradeoff by maximizing the volumes while guaranteeing a minimum Return On Investment (ROI) level. Such a task can be naturally modeled as a combinatorial optimization problem subject to ROI and budget constraints that can be solved online. In this picture, the learner's uncertainty over the constraints' parameters plays a crucial role since the algorithms' exploration choices might lead to their violation during the entire learning process. Such violations represent a major obstacle to adopting online techniques in real-world applications. Thus, controlling the algorithms' exploration during learning is paramount to making humans trust online learning tools. This paper studies the nature of both optimization and learning problems. In particular, we show that the learning problem is inapproximable within any factor (unless P = NP) and provide a pseudo-polynomial-time algorithm to solve its discretized version. Subsequently, we prove that no online learning algorithm can violate the (ROI or budget) constraints a sublinear number of times during the learning process while guaranteeing a sublinear regret. We provide the $GCB$ algorithm that guarantees sublinear regret at the cost of a linear number of constraint violations and $GCB_{safe}$ that guarantees w.h.p. a constant upper bound on the number of constraint violations at the cost of a linear regret. Moreover, we designed $GCB_{safe}(ψ,ϕ)$, which guarantees both sublinear regret and safety w.h.p. at the cost of accepting tolerances $ψ$ and $ϕ$ in the satisfaction of the ROI and budget constraints, respectively. Finally, we provide experimental results to compare the regret and constraint violations of $GCB$, $GCB_{safe}$, and $GCB_{safe}(ψ,ϕ)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_07139 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Safe Online Bid Optimization with Return on Investment and Budget Constraints Castiglioni, Matteo Nuara, Alessandro Romano, Giulia Spadaro, Giorgio Trovò, Francesco Gatti, Nicola Machine Learning Artificial Intelligence In online marketing, the advertisers aim to balance achieving high volumes and high profitability. The companies' business units address this tradeoff by maximizing the volumes while guaranteeing a minimum Return On Investment (ROI) level. Such a task can be naturally modeled as a combinatorial optimization problem subject to ROI and budget constraints that can be solved online. In this picture, the learner's uncertainty over the constraints' parameters plays a crucial role since the algorithms' exploration choices might lead to their violation during the entire learning process. Such violations represent a major obstacle to adopting online techniques in real-world applications. Thus, controlling the algorithms' exploration during learning is paramount to making humans trust online learning tools. This paper studies the nature of both optimization and learning problems. In particular, we show that the learning problem is inapproximable within any factor (unless P = NP) and provide a pseudo-polynomial-time algorithm to solve its discretized version. Subsequently, we prove that no online learning algorithm can violate the (ROI or budget) constraints a sublinear number of times during the learning process while guaranteeing a sublinear regret. We provide the $GCB$ algorithm that guarantees sublinear regret at the cost of a linear number of constraint violations and $GCB_{safe}$ that guarantees w.h.p. a constant upper bound on the number of constraint violations at the cost of a linear regret. Moreover, we designed $GCB_{safe}(ψ,ϕ)$, which guarantees both sublinear regret and safety w.h.p. at the cost of accepting tolerances $ψ$ and $ϕ$ in the satisfaction of the ROI and budget constraints, respectively. Finally, we provide experimental results to compare the regret and constraint violations of $GCB$, $GCB_{safe}$, and $GCB_{safe}(ψ,ϕ)$. |
| title | Safe Online Bid Optimization with Return on Investment and Budget Constraints |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2201.07139 |