Title: Conservative Exploration using Interleaving,
Abstract: In many practical problems, a learning agent may want to learn the best
action in hindsight without ever taking a bad action, which is significantly
worse than the default production action. In general, this is impossible
because the agent has to explore unknown actions, some of which can be bad, to
learn better actions. However, when the actions are combinatorial, this may be
possible if the unknown action can be evaluated by interleaving it with the
production action. We formalize this concept as learning in stochastic
combinatorial semi-bandits with exchangeable actions. We design efficient
learning algorithms for this problem, bound their n-step regret, and evaluate
them on both synthetic and real-world problems. Our real-world experiments show
that our algorithms can learn to recommend K most attractive movies without
ever violating a strict production constraint, both overall and subject to a
diversity constraint.