  In online marketing, the advertisers' goal is usually a tradeoff between
achieving high volumes and high profitability. The companies' business units
customarily address this tradeoff by maximizing the volumes while guaranteeing
a lower bound to the Return On Investment (ROI). This paper investigates
combinatorial bandit algorithms for the bid optimization of advertising
campaigns subject to uncertain budget and ROI constraints. We study the nature
of both the optimization and learning problems. In particular, when focusing on
the optimization problem without uncertainty, we show that it is inapproximable
within any factor unless P=NP, and we provide a pseudo-polynomial-time
algorithm that achieves an optimal solution. When considering uncertainty, we
prove that no online learning algorithm can violate the (ROI or budget)
constraints during the learning process a sublinear number of times while
guaranteeing a sublinear pseudo-regret. Thus, we provide an algorithm, namely
GCB, guaranteeing sublinear regret at the cost of a potentially linear number
of constraints violations. We also design its safe version, namely GCB_{safe},
guaranteeing w.h.p. a constant upper bound on the number of constraints
violations at the cost of a linear pseudo-regret. More interestingly, we
provide an algorithm, namely GCB_{safe}(\psi,\phi), guaranteeing both sublinear
pseudo-regret and safety w.h.p. at the cost of accepting tolerances \psi and
\phi in the satisfaction of the ROI and budget constraints, respectively. This
algorithm actually mitigates the risks due to the constraints violations
without precluding the convergence to the optimal solution. Finally, we
experimentally compare our algorithms in terms of
pseudo-regret/constraint-violation tradeoff in settings generated from
real-world data, showing the importance of adopting safety constraints in
practice and the effectiveness of our algorithms.
