Generalization bounds for minimum volume set estimation based on Markovian data

The main goal of this paper is to establish generalization bounds for minimum volume set estimation for regenerative Markov chains. We obtain new maximal concentration inequality in order to show that learning rate bounds depend not only on the complexity of the class of candidate sets but also on the ergodicity rate of the chain X, expressed in terms of tail conditions for the length of the regenerative cycles. Finally, we show that it is straightforward to extend the preceding results to the Harris recurrent case.