Minimax Learning of Ergodic Markov Chains
Abstract
We compute the finite-sample 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 finite-sample estimators with fully empirical confidence intervals. To our knowledge, this is the first PAC-type result with nearly matching (up to logarithmic factors) upper and lower bounds for learning, in any metric, in the context of Markov chains.
Cite
Text
Wolfer and Kontorovich. "Minimax Learning of Ergodic Markov Chains." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.Markdown
[Wolfer and Kontorovich. "Minimax Learning of Ergodic Markov Chains." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.](https://mlanthology.org/alt/2019/wolfer2019alt-minimax/)BibTeX
@inproceedings{wolfer2019alt-minimax,
title = {{Minimax Learning of Ergodic Markov Chains}},
author = {Wolfer, Geoffrey and Kontorovich, Aryeh},
booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory},
year = {2019},
pages = {904-930},
volume = {98},
url = {https://mlanthology.org/alt/2019/wolfer2019alt-minimax/}
}