Feasible Bidding Strategies through Pure Exploration Bandits

We apply and extend recent results in feasible arm identi󰎓 cation to quickly󰎓 nd a small set of bidding strategies that can simultaneously meet multiple business objectives. We formulate this as an any-m feasible arm identi󰎓 cation 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 P “tx: Ax ď bu Ă RD. This problem has many applications beyond advertising to online A/B testing, crowdsourcing, clinical trials, and hyperparameter optimization. We propose a new formal algorithm and explore a heuristic improvement through synthetic and real-world datasets.