Minimax Learning of Ergodic Markov Chains
[edit]
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:904930, 2019.
Abstract
We compute the finitesample minimax (modulo logarithmic factors) sample complexity of learning the parameters of a finite Markov chain from a single long sequence of states. Our error metric is a natural variant of total variation. The sample complexity necessarily depends on the spectral gap and minimal stationary probability of the unknown chain, for which there are known finitesample estimators with fully empirical confidence intervals. To our knowledge, this is the first PACtype result with nearly matching (up to logarithmic factors) upper and lower bounds for learning, in any metric, in the context of Markov chains.
Related Material


