Feasible Bidding Strategies through Pure Exploration Bandits
Abraham Bagherjeiran and Juliann Katz-Samuels
We apply and extend recent results in feasible arm identification to quickly find a small set of bidding strategies that can simultaneously meet multiple business objectives. We formulate this as the any-m feasible arm identification problem, a pure exploration multi-armed bandit problem where each arm is a D-dimensional distribution represented by a mean vector. The goal is to identify m feasible arms, meaning they satisfy a set of multiple criteria, represented by a polyhedron. This problem has many applications beyond advertising to general online A/B testing, crowdsourcing, clinical trials, and hyperparameter optimization. We propose a new formal algorithm and explore a heuristic improvement through various synthetic and real-world datasets.