Motivated by programmatic advertising optimization, consider the task of allocating budgets to a set of resources in sequence. At every time step, viable assignments are chosen and only corresponding random returns are observed. The goal is to maximize the cumulative expected sum of returns. This is a realistic model for budget allocation across marketing campaign subdivisions when the goal is to maximize conversions. We study a direct search (aka pattern search) method for linearly constrained, derivative-free optimization in the presence of noise. These algorithms are easy to implement and are particularly suitable for constrained optimization. They have not yet been analyzed in terms of cumulative regret. It provides a regret upper bound of the order of T 2/3 in the general case. Our mathematical analysis also establishes, as a by-product, time-independent regret bounds in the deterministic and unconstrained case. We also propose an improved version of the method that relies on sequential testing to accelerate descent direction identification.
