  We consider model selection for sequential decision making in stochastic
environments with bandit feedback, where a meta-learner has at its disposal a
pool of base learners, and decides on the fly which action to take based on the
policies recommended by each base learner. Model selection is performed by
regret balancing but, unlike the recent literature on this subject, we do not
assume any prior knowledge about the base learners like candidate regret
guarantees; instead, we uncover these quantities in a data-driven manner. The
meta-learner is therefore able to leverage the realized regret incurred by each
base learner for the learning environment at hand (as opposed to the expected
regret), and single out the best such regret. We design two model selection
algorithms operating with this more ambitious notion of regret and, besides
proving model selection guarantees via regret balancing, we experimentally
demonstrate the compelling practical benefits of dealing with actual regrets
instead of candidate regret bounds.
