PAC-Bayesian Analysis of the Exploration-Exploitation Trade-off

We develop a coherent framework for integrative simultaneous analysis of the explorationexploitation and model order selection tradeoffs. We improve over our preceding results on the same subject (Seldin et al., 2011) by combining PAC-Bayesian analysis with Bernstein-type inequality for martingales. Such a combination is also of independent interest for studies of multiple simultaneously evolving martingales.