Minimax Learning of Ergodic Markov Chains

  • 2018-09-13 15:37:19
  • Geoffrey Wolfer, Aryeh Kontorovich
  • 1


We compute the finite-sample minimax (modulo logarithmic factors) samplecomplexity of learning the parameters of a finite Markov chain from a singlelong sequence of states. Our error metric is a natural variant of totalvariation. The sample complexity necessarily depends on the spectral gap andminimal stationary probability of the unknown chain - for which, at least inthe reversible case, there are known finite-sample estimators with fullyempirical confidence intervals. To our knowledge, this is the first PAC-typeresult with nearly matching (up to logs) upper and lower bounds for learning,in any metric in the context of Markov chains.


Introduction (beta)



Conclusion (beta)