  Most PAC-Bayesian bounds hold in the batch learning setting where data is
collected at once, prior to inference or prediction. This somewhat departs from
many contemporary learning problems where data streams are collected and the
algorithms must dynamically adjust. We prove new PAC-Bayesian bounds in this
online learning framework, leveraging an updated definition of regret, and we
revisit classical PAC-Bayesian results with a batch-to-online conversion,
extending their remit to the case of dependent data. Our results hold for
bounded losses, potentially \emph{non-convex}, paving the way to promising
developments in online learning.
